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.

http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/ch2m1fr.html
http://geekz.fr/Definitions-sur-les-graphes
http://www.mathematiquesfaciles.com/graphes-chaine-eulerienne-niveau-t-es_2_45326.htm