Cette section présente pour commencer la notion de graphe orienté en introduisant conjointement la notion de graphe et d'orientation.

Définition de graphe orienté

Le graphe $G$ peut se représenter de la façon suivante :

$G=(X,U)$

$$\begin{gathered} X \\ subseteqU \\ timesU \end{gathered}$$

Avec :

$$\begin{gathered} X= \\ Sommets \\ = \\ 1,2,3,4,5 \end{gathered}$$

$$\begin{gathered} U= \\ Arcs \\ = \\ (1,2),(1,3),(2,2),(2,5),(4,2),(4,3),(4,5) \end{gathered}$$

Définition de successeur et prédécesseur

Définition de successeur

Soit $mathcal{T}^{+}(S)$, l'ensemble des successeurs de $S$ (ie les sommets $Y$ tels que $$\begin{gathered} (S,Y) \\ inU \end{gathered}$$)

On a donc : \\mathcal{T}^{+} & : & X & \\to & P \\\\ où $$\begin{gathered} P \\ subseteqU \end{gathered}$$

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

Définition de prédécesseur

Soit $mathcal{T}^{-}(S)$, l'ensemble des prédecessuers de $S$ (ie les sommets $Y$ tels que $$\begin{gathered} (Y,S) \\ inU \end{gathered}$$)

On a donc : \\mathcal{T}^{-} & : & X & \\to & P \\\\ où $$\begin{gathered} P \\ subseteqU \end{gathered}$$

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\\}

Définition de demi-degré intérieur et demi degré-extérieur

Définition de demi-degré extérieur

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

Définition de demi-degré intérieur

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

Définition de chemin et de boucle

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ù $$\begin{gathered} S \\ inX \end{gathered}$$

Définition de circuit

Prenons le nouveau graphe $G\_2$ suivant :

$G\_2=(X\_2,U\_2)$

Avec :

$$\begin{gathered} X\_2= \\ 1,2,3,4,5,6 \end{gathered}$$

$$\begin{gathered} U\_2= \\ (1,2),(2,4),(4,1),(2,3),(5,4),(3,6),(5,6) \end{gathered}$$

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)$

Définition de chemin Hamiltonien

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)

Graphe Non Orienté

Définition de graphe non orienté

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.

$$\begin{gathered} X\_3= \\ Sommets \\ = \\ 1,2,3,4,5 \end{gathered}$$

$$\begin{gathered} U\_3= \\ Arr\hat{e}tes \\ = \\ 1,2 \\ , \\ 1,3 \\ , \\ 2,3 \\ , \\ 3,4, \\ , \\ 4,5 \end{gathered}$$

Définition d'une chaîne

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).

Définition d'adjacence

Un sommet $Y$ est voisin ou adjoint d'un sommet $S$ si $$\begin{gathered} Y,S \\ inU \end{gathered}$$

Exemple : $3$ a comme voisins $1,2$ et $4$

On note $mathcalT(S)$, l'ensemble des voisins ou adjoints de $S$

Dans notre exemple : $$\begin{gathered} mathcalT(S)= \\ 1,2,3 \end{gathered}$$

Définition de degré

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

Définition de cycle

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.

Définition de chaîne Eulérienne

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.

Théorème d'Euler

Un graphe /divers/cours/theorie_des_graphes_et_optimisation_dans_les_graphes/connexite_forte_connexite_fermeture_transitive 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.

Sources

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