====== Graphe Orienté ====== 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é ===== {{http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/img/Image4.gif?270}} 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)\}$\\ \\ ===== 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 $(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$\\ ==== Définition de prédécesseur ==== 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\}$\\ ===== 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ù $S \in X$ ===== Définition de circuit ===== Prenons le nouveau graphe $G_{2}$ suivant : {{http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/img/Image9.gif?270}} $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)$\\ ===== 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 {{http://geekz.fr/IMG/png/09.png?270}} 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 : {{http://www.geog.umontreal.ca/geotrans/fr/ch2fr/meth2fr/img/Image14.gif?270}} $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\}\}$\\ \\ ===== 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 $\{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\}$ ===== 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 {{http://www.anglaisfacile.com/cgi2/myexam/images/21624.jpg?300}} $(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|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. ====== 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\\