Cette section présente pour commencer la notion de graphe orienté en introduisant conjointement la notion de graphe et d'orientation.
Le graphe $G$ peut se représenter de la façon suivante :
$G=(X,U)$
$X \subseteq U \times U$
Avec :
$X=\{Sommets\}=\{1,2,3,4,5\}$
$U=\{Arcs\}=\{(1,2),(1,3),(2,2),(2,5),(4,2),(4,3),(4,5)\}$
Soit $\mathcal{T}^{+}(S)$, l'ensemble des successeurs de $S$ (ie les sommets $Y$ tels que $(S,Y) \in U$)
On a donc : $\mathcal{T}^{+} & : & X & \to & P \\$ où $P \subseteq U$
En reprenant notre exemple, nous avons :
$\mathcal{T}^{+}(1) & = & \{2,3\}$
$\mathcal{T}^{+}(2) & = & \{2,5\}$
$\mathcal{T}^{+}(3) & = & \varnothing$
$\mathcal{T}^{+}(4) & = & \{3,2,5\}$
$\mathcal{T}^{+}(5) & = & \varnothing$
Soit $\mathcal{T}^{-}(S)$, l'ensemble des prédecessuers de $S$ (ie les sommets $Y$ tels que $(Y,S) \in U$)
On a donc : $\mathcal{T}^{-} & : & X & \to & P \\$ où $P \subseteq U$
En reprenant notre exemple, nous avons :
$\mathcal{T}^{-}(1) & = & \varnothing$
$\mathcal{T}^{-}(2) & = & \{2,1,4\}$
$\mathcal{T}^{-}(3) & = & \{1,4\}$
$\mathcal{T}^{-}(4) & = & \varnothing$
$\mathcal{T}^{-}(5) & = & \{2,4\}$
Le demi-degré extérieur noté $d^{+}(S)$ d'un sommet $S$ est le nombre de successeurs du sommet $S$ : $d^{+}(S)=\#\mathcal{T}^{+}(S)$
Exemple :
$d^{+}(1)=\#\mathcal{T}^{+}(1) & = & \#\{2,3\} = 2$
$d^{+}(2)=\#\mathcal{T}^{+}(2) & = & \#\{2,5\} = 2 $
$d^{+}(3)=\#\mathcal{T}^{+}(3) & = & \#\varnothing = 0$
$d^{+}(4)=\#\mathcal{T}^{+}(4) & = & \#\{3,2,5\} = 3 $
$d^{+}(5)=\#\mathcal{T}^{+}(5) & = & \#\varnothing = 0$
Le demi-degré intérieur noté $d^{-}(S)$ d'un sommet $S$ est le nombre de prédécesseur du sommet $S$ : $d^{-}(S)=\#\mathcal{T}^{-}(S)$
Exemple :
$d^{-}(1)=\#\mathcal{T}^{-}(1) & = & \#\varnothing = 0$
$d^{-}(2)=\#\mathcal{T}^{-}(2) & = & \#\{2,1,4\} = 3$
$d^{-}(3)=\#\mathcal{T}^{-}(3) & = & \#\{1,4\} = 2$
$d^{-}(4)=\#\mathcal{T}^{-}(4) & = & \#\varnothing = 0$
$d^{-}(5)=\#\mathcal{T}^{-}(5) & = & \#\{2,4\} = 2$
Un chemin est une suite d'arcs tel que l'extrémité terminale d'un arc coïncide avec l’extrémité initiale du suivant.
Dans notre exemple nous avons comme chemin : $((1,2),(2,2),(2,5))=((1,2,2,5))$ ou $((4,2),(2,5))=(4,2,5)$
Une boucle est un arc du type $(S,S)$ où $S \in X$
Prenons le nouveau graphe $G_{2}$ suivant :
$G_{2}=(X_{2},U_{2})$
Avec :
$X_{2}=\{1,2,3,4,5,6\}$
$U_{2}=\{(1,2),(2,4),(4,1),(2,3),(5,4),(3,6),(5,6)\}$
Un circuit est un chemin dont le premier sommet coïncide avec le dernier et qui ne passe pas 2 fois par le même arc.
Il y a 2 circuits dans ce graphe qui sont :
$((1,2),(2,4),(4,1)) = (1,2,4,1)$
$((1,2),(2,5),(5,4),(4,1)) = (1,2,5,4,1)$
Un chemin Hamiltonien dans un graphe est un chemin qui passe une et une seule fois par chaque sommet du graphe
Le chemin (1,2,3,5,4,1) est un chemin Hamiltonien (Le sommet 1 étant inscrit en double pour montrer la jointure)
Le graphe $G_{3}$ peut se représenter de la façon suivante :
$G_{3}=(X_{3},U_{3})$
$U_{3}$ représente cette fois ci des arrêtes, car il n'y a pas d'orientation.
$X_{3}=\{Sommets\}=\{1,2,3,4,5\}$
$U_{3}=\{Arrêtes\}=\{\{1,2\},\{1,3\},\{2,3\},\{3,4,\},\{4,5\}\}$
Une chaîne est une suite d'arrête telle que toute arrête a une extrémité commune avec l'arrête précédente (sauf la première) et l'autre avec l'arrête suivante (sauf la dernière).
Un sommet $Y$ est voisin ou adjoint d'un sommet $S$ si $\{Y,S\} \in U$
Exemple : $3$ a comme voisins $1,2$ et $4$
On note $\mathcal{T}(S)$, l'ensemble des voisins ou adjoints de $S$
Dans notre exemple : $\mathcal{T}(S) = \{1,2,3\}$
Le degré noté $d(S)$ d'un sommet $S$ est le nombre de voisins du sommet $S$ : $d(S)=\#\mathcal{T}(S)$
Exemple :
$d(1)=#\mathcal{T}(1)=\#\{2,3\}=2$
$d(2)=#\mathcal{T}(2)=\#\{1,3\}=2$
$d(3)=#\mathcal{T}(3)=\#\{1,2,4\}=3$
$d(4)=#\mathcal{T}(4)=\#\{3,5\}=2$
$d(5)=#\mathcal{T}(5)=\#\{4\}=1$
Un cycle est une chaîne dont les 2 extrémités coîncident et qui ne passe pas 2 fois par la même arrête.
Exemple : $(1,2,3,1)$ est un cycle.
Une chaine eulérienne est une chaîne qui passe une et une seule fois par chaque arrête
$(1,2,5,4,3,1)$ est une chaîne eulérienne.
Un graphe connexe admet une chaîne eulérienne ssi le nombre de sommets de degrés impairs est de 0 ou de 2.
Pour un graphe connexe $G$, $\exists$ chaîne eulérienne dans $G \Leftrightarrow \#\{S \in X, d(S)=1[2]\} \in \{0,2\}$
Il suffit donc de calculer le degré de tous les sommets et de dénombrer ceux qui sont impaires et de voir si le résultat est 0 ou 2.
Dans notre exemple :
$d(1)=2$
$d(2)=3$
$d(3)=3$
$d(4)=2$
$d(5)=2$
Le nombre de sommets de degrés impairs étant de $2$ (le sommet $2$ et le sommet $3$), il existe bien une chaîne eulérienne dans ce graphe.