Lernzettel: Introduction aux graphes et parcours

📋 Plan du Cours

1. Connexité et composantes connexes
2. Parcours des graphes
3. Parcours orienté et successeurs
4. File FIFO
5. Parcours en largeur
6. Plus court chemin
7. Connexité par parcours en largeur
8. Exercice final

📖 1. Connexité et composantes connexes

🔑 Notions clés & Définitions

• Graphe connexe : Un graphe est connexe si, pour toute paire de sommets, il existe une chaîne qui permet de passer de l’un à l’autre.
• Composantes connexes : Des composantes connexes sont des sous-ensembles de sommets dans lesquels la connexité existe, même si le graphe global n’est pas connexe.

📝 Points essentiels

• Un graphe $G=(X,U)$ est connexe ssi il existe une chaîne reliant toute paire de sommets $x$ et $y$.
• Dans un graphe non connexe, on peut regrouper les sommets en composantes connexes formées par des sous-ensembles distincts.
• Pour tester la connexité, on s’appuie sur des parcours qui visent à relier des sommets via des chaînes ou chemins successifs.

📖 2. Parcours des graphes

🔑 Notions clés & Définitions

• Parcours : Un parcours est une méthode systématique qui visite des sommets et suit l’évolution de leur état jusqu’à ce que tous les sommets aient été traités.
• Ordre de prévisite : L’ordre de prévisite est la suite dans laquelle les sommets sont découverts (ouverts) au cours du parcours.
• Ordre de postvisite : L’ordre de postvisite est la suite dans laquelle les sommets sont fermés au cours du parcours.

📝 Points essentiels

• Le parcours commence avec tous les sommets non marqués puis répète : choisir un sommet non marqué et l’ouvrir/fermer selon ses voisins.
• On ferme un sommet $x$ quand tous ses sommets adjacents sont ouverts ou fermés.
• Les listes d’exemple données montrent que la prévisite et la postvisite ne sont pas forcément identiques (prévisite {A, B, D, C, E, F, G, H} et postvisite {A, C, B, D, E, F, G, H}).
• Si le parcours depuis un sommet ne couvre pas tout, on recommence depuis un autre sommet non relié aux déjà traités.

📖 3. Parcours orienté et successeurs

🔑 Notions clés & Définitions

• Graphe orienté : Un graphe orienté représente les relations par des arcs, et l’orientation influence ce qu’on peut atteindre à partir d’un sommet.
• Successeur : Un successeur d’un sommet est un sommet atteignable directement depuis lui en suivant un arc.

📝 Points essentiels

• Dans un graphe orienté, l’algorithme de parcours remplace la notion d’adjacent par la notion de successeur.
• On ouvre un sommet $y$ non marqué s’il est successeur d’un sommet $x$ déjà ouvert.
• On ferme un sommet $x$ quand tous ses successeurs sont ouverts ou fermés.
• Pour déterminer la connexité en orienté, on peut occulter l’orientation et considérer les arcs comme des arêtes lors du test par parcours en largeur.

📖 4. File FIFO

🔑 Notions clés & Définitions

• File : Une file est une structure de données ordonnée sur laquelle on retire uniquement l’élément en tête et on ajoute uniquement en queue.
• File FIFO : Une file FIFO (First In First Out) traite d’abord les éléments arrivés en premier, car ils sont retirés depuis la tête.

📝 Points essentiels

• Une file FIFO réalise deux opérations : suppression de la tête et insertion en queue.
• Le rôle de la file est central dans le parcours en largeur pour respecter l’ordre de traitement des sommets.
• La logique de file correspond à une file d’attente : entrée par la queue et sortie par la tête.

📖 5. Parcours en largeur

🔑 Notions clés & Définitions

• Parcours en largeur : Le parcours en largeur est un parcours qui explore progressivement un graphe par couches à l’aide d’une file FIFO.
• Prévisiter : Prévisiter un sommet signifie l’ouvrir et l’ajouter pour un traitement futur selon la file.
• Postvisiter : Postvisiter un sommet signifie fermer le sommet une fois que ses successeurs ont été mis en file.

📝 Points essentiels

• Le parcours en largeur utilise une file : on prévisite un sommet non marqué puis on le met en file.
• Tant que la file n’est pas vide, on retire le sommet $x$ en tête, puis on met en file tous ses successeurs $y$ non marqués.
• Quand tous les successeurs de $x$ ont été traités (mis en file), on postvise (ferme) $x$.
• Les exemples du cours donnent pour un cas : prévisite A, B, C, F, D, E et postvisite A, B, C, F, D, E.

📖 6. Plus court chemin

🔑 Notions clés & Définitions

• Plus court chemin : Le plus court chemin entre deux sommets est le chemin qui minimise le nombre d’arcs (ou arêtes) rencontrés.
• Distance $d(x)$ : La distance $d(x)$ est une valeur associée aux sommets qui permet de mémoriser le nombre d’arcs depuis le sommet initial pendant l’algorithme.

📝 Points essentiels

• Dans ce cours, la longueur d’une chaîne correspond au nombre d’arcs (ou d’arêtes) rencontrés.
• On initialise $d(x)=0$ pour le sommet initial $x$ puis, lors de l’exploration, on affecte $d(y)=d(x)+1$ pour chaque successeur $y$ nouvellement mis en file.
• L’algorithme du plus court chemin s’appuie sur le parcours en largeur et une file FIFO pour explorer par niveaux.
• Le déroulé est décrit comme identique au parcours précédent, avec uniquement une incrémentation de la valeur $d$ à chaque étape.

📖 7. Connexité par parcours en largeur

🔑 Notions clés & Définitions

• Graphe symétrique : Un graphe symétrique est obtenu en rendant un graphe orienté équivalent en remplaçant chaque arc par une relation bidirectionnelle.
• Arborescence : Une arborescence correspond à un ensemble de sommets atteints depuis un sommet de départ lors du parcours, formant une couverture cohérente.

📝 Points essentiels

• Pour un graphe orienté, on teste la connexité en occultant l’orientation des arcs (on les considère comme des arêtes).
• Pendant le parcours en largeur, si la file ne se vide qu’au tout début puis à la toute fin, le graphe est connexe.
• Si la file se vide au milieu, le graphe n’est pas connexe et il se décompose en plusieurs composantes connexes correspondant à des arborescences trouvées.
• Un exemple donne deux composantes connexes {A, B, C, E} et {D} quand la file devient vide en plein déroulement.

📖 8. Exercice final

🔑 Notions clés & Définitions

• Connexité : La connexité est la propriété d’un graphe où une chaîne relie toute paire de sommets.
• Chemin de A à C : Le chemin de A à C est évalué via le plus court chemin, en minimisant le nombre d’arcs ou d’arêtes rencontrés.

📝 Points essentiels

• L’exercice demande d’indiquer si le graphe fourni est connexe.
• L’exercice demande aussi la valeur du plus court chemin pour aller de A à C.
• La correction attend des réponses issues directement des tests par parcours en largeur (connexité) et du calcul de distances (plus court chemin).

⚠️ Pièges & confusions fréquents

1. Confondre connexité (existence d’une chaîne entre toute paire) et parcours (méthode de visite), car un parcours partiel implique souvent des composantes distinctes.
2. Utiliser adjacent au lieu de successeur dans le cas orienté : l’orientation change ce qu’on peut atteindre.
3. Croire que la prévisite et la postvisite sont toujours les mêmes, alors que les exemples montrent des ordres différents.
4. Oublier l’initialisation $d(x)=0$ au sommet initial dans le plus court chemin, ce qui fausse la valeur $d(y)=d(x)+1$.
5. Conclure à la connexité d’un graphe orienté sans rendre le graphe symétrique dans la méthode du cours.
6. Se tromper sur le critère file vide au milieu : cela indique la non-connexité et non un simple changement d’ordre d’exploration.

✅ Checklist Examen

1. Définir ce qu’est un graphe connexe en termes de chaîne reliant toute paire de sommets.
2. Expliquer ce que sont des composantes connexes quand un graphe n’est pas connexe.
3. Décrire le schéma général de parcours avec états non marqués puis ouverture/fermeture selon la condition sur les voisins.
4. Donner la différence d’algorithme entre graphe non orienté (adjacent) et graphe orienté (successeur).
5. Définir une file et sa logique FIFO en termes de tête et de queue.
6. Énoncer les étapes du parcours en largeur : prévisiter et insérer dans la file, puis retirer en tête et insérer les successeurs non marqués.
7. Calculer la distance $d(y)$ dans l’algorithme du plus court chemin à partir de $d(x)$ avec la relation $d(y)=d(x)+1$.
8. Conclure la connexité par parcours en largeur : file vidée seulement au début et à la fin implique connexe, sinon non connexe.
9. Relier le test de connexité orientée au graphe symétrique en occultant l’orientation des arcs.
10. Résoudre l’exercice final en utilisant : parcours en largeur pour la connexité et distances pour le plus court chemin de A à C.