• Afficher la page
  • Anciennes révisionsLiens de retour

    • Différences

    Ci-dessous, les différences entre deux révisions de la page.

    Lien vers cette vue comparative

    Les deux révisions précédentesRévision précédente
    Prochaine révision    		Révision précédente
    divers:cours:theorie_des_graphes_et_optimisation_dans_les_graphes:definitions_de_base_parcours_de_graphe [2023/08/30 19:18] – supprimée - modification externe (Unknown date) 127.0.0.1divers:cours:theorie_des_graphes_et_optimisation_dans_les_graphes:definitions_de_base_parcours_de_graphe [2023/08/30 19:18] (Version actuelle) – ↷ Liens modifiés en raison d'un déplacement. de-weerd2022
    Ligne 1: Ligne 1:
     +====== 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\\