Lernzettel: Introduction aux graphes et parcours

📋 Plan du Cours

1. Exemples introductifs
2. Définitions graphes
3. Représentation en Python
4. Parcours en largeur
5. Parcours en profondeur
6. Recherche de cycles

📖 1. Exemples introductifs

🔑 Notions clés & Définitions

• Réseaux sociaux : Représentés par un graphe où les sommets sont des individus ou entités, et les arêtes (ou arcs) indiquent des relations ou interactions entre eux. Exemple : un graphe avec une grosse composante connexe montre une communauté fortement reliée.

• Réseau routier, carte : Modélisation d’un espace géographique sous forme de graphe où chaque sommet représente un lieu, et chaque arête une route reliant deux lieux. Si les routes ont un sens, le graphe est orienté.

• Labyrinthe : Modélisé par un graphe dont les sommets sont des points ou intersections, et les arêtes représentent les passages possibles. La modélisation peut révéler des îlots ou zones inaccessibles, et permet d’appliquer des parcours pour résoudre des problèmes d’évasion ou de navigation.

• Graphe de positions : Graphe où chaque sommet représente une configuration ou une position dans un jeu. Si aucune position ne se répète, ce graphe est un arbre sans cycle. Les feuilles correspondent à des états finaux (victoire, défaite, nul). La stratégie consiste à remonter depuis ces feuilles pour déterminer le résultat optimal.

• Graphe de dépendances : Graphe orienté où chaque sommet est un module ou une étape, et chaque arc indique une dépendance ou un prérequis. Utilisé notamment en compilation ou en gestion de projets, il doit être exempt de cycles pour assurer une progression logique.

📝 Points essentiels

• Les exemples illustrent comment modéliser des situations concrètes par des graphes : réseaux sociaux, routiers, labyrinthes, positions de jeu, dépendances.
• La modélisation par graphe permet d’appliquer des parcours (en largeur ou en profondeur) pour résoudre des problèmes spécifiques.
• La présence ou absence de cycle dans un graphe de positions ou de dépendances influence la faisabilité ou la stratégie à adopter.
• La modélisation sous forme de graphe de positions dans un jeu permet de prouver l’existence d’un résultat (victoire, défaite, nul) en utilisant la structure arborescente.

💡 À retenir

Les exemples introductifs montrent que la modélisation par graphe est une méthode puissante pour représenter et analyser des situations variées, en utilisant des parcours et en vérifiant l’absence de cycles pour garantir la cohérence ou la stratégie optimale.

📖 2. Définitions graphes

🔑 Notions clés & Définitions

• Graphe non orienté : Un ensemble fini de sommets reliés entre eux par des arêtes, noté 𝐺=(𝑉,𝐸), où 𝑉 est l'ensemble des sommets et 𝐸 l'ensemble des arêtes, chaque arête étant une paire de sommets distincts {s, t}.
• Graphe orienté : Un ensemble fini de sommets reliés par des arcs, noté 𝐺=(𝑉,𝐸), où 𝑉 est l'ensemble des sommets et 𝐸 un ensemble de couples (s, t) représentant un arc allant de s à t.
• Sommet : Un élément de l'ensemble 𝑉, représentant un point ou un nœud dans le graphe.
• Arête : Une paire de sommets {s, t} dans un graphe non orienté, représentant une connexion sans sens précis.
• Arc : Un couple (s, t) dans un graphe orienté, représentant une connexion avec un sens allant de s vers t.

📝 Points essentiels

• Dans un graphe non orienté, chaque arête {s, t} relie deux sommets sans direction. La somme des degrés des sommets est égale à deux fois le nombre d’arêtes (∑𝑠∈𝑉 𝑑(𝑠) = 2 * |𝐸|).
• Dans un graphe orienté, chaque arc (s, t) a une origine s et une cible t. Le degré sortant 𝑑+(𝑠) correspond au nombre de successeurs de s, et le degré entrant 𝑑−(𝑠) au nombre de prédécesseurs.
• La représentation d’un graphe peut se faire via une matrice d’adjacence (liste de listes) ou un dictionnaire d’adjacence (clé : sommet, valeur : liste des successeurs).
• La matrice d’adjacence 𝑀[𝑖][𝑗] est un booléen indiquant la présence ou l’absence d’une arête ou arc entre les sommets 𝑖 et 𝑗.
• Le dictionnaire d’adjacence 𝐷 associe chaque sommet à la liste de ses successeurs (pour un graphe orienté) ou voisins (pour un graphe non orienté).

💡 À retenir

Un graphe est une structure composée de sommets et d’arêtes ou arcs, dont la représentation peut varier (matrice ou dictionnaire), et dont la nature orientée ou non orientée influence la définition des relations entre sommets.

📖 3. Représentation en Python

🔑 Notions clés & Définitions

• Représentation en Python : méthode de modélisation d’un graphe en utilisant des structures de données Python, telles que listes ou dictionnaires, pour faciliter l’implémentation des algorithmes de parcours ou d’analyse.

• Matrice d’adjacence : liste de listes en Python où chaque élément M[i][j] indique la présence ou l’absence d’une arête ou d’un arc entre le sommet i et le sommet j. Si une arête existe, la valeur est True ou une valeur équivalente ; sinon, False.

• Dictionnaire d’adjacence : dictionnaire Python où chaque clé est un sommet du graphe, et la valeur associée est la liste des successeurs (pour un graphe orienté) ou des voisins (pour un graphe non orienté).

• Liste des voisins : liste contenant tous les sommets adjacents à un sommet donné dans un graphe non orienté, ou tous les successeurs/prédécesseurs dans un graphe orienté, selon la structure de représentation.

• Liste des successeurs : liste des sommets accessibles directement depuis un sommet donné dans un graphe orienté, c’est-à-dire tous v tels que (s, v) appartient à E.

• Liste des prédécesseurs : liste des sommets ayant une arête ou un arc allant vers un sommet donné dans un graphe orienté, c’est-à-dire tous v tels que (v, s) appartient à E.

📝 Points essentiels

• La matrice d’adjacence est représentée par une liste de listes, où chaque élément M[i][j] vaut True si une arête ou un arc relie i à j, sinon False. La commande len(M) donne l’ordre du graphe (nombre de sommets).

• Le dictionnaire d’adjacence associe à chaque sommet une liste de ses successeurs ou voisins, facilitant l’accès direct aux successeurs d’un sommet donné.

• La liste des voisins s’obtient en parcourant la ligne correspondante dans la matrice d’adjacence ou en accédant à la liste dans le dictionnaire d’adjacence.

• La liste des successeurs dans un dictionnaire d’adjacence est directement la valeur associée à la clé du sommet dans le dictionnaire.

• La liste des prédécesseurs dans un graphe orienté se construit en parcourant le dictionnaire d’adjacence : pour chaque sommet, on vérifie dans tous les autres si ce sommet apparaît dans leur liste de successeurs.

💡 À retenir

Les représentations en Python, telles que la matrice d’adjacence et le dictionnaire d’adjacence, offrent deux approches complémentaires pour modéliser un graphe : la première privilégie la simplicité d’accès par indices, la seconde facilite la gestion dynamique et l’accès direct aux successeurs ou voisins.

📖 4. Parcours en largeur

🔑 Notions clés & Définitions

• Parcours en largeur : méthode d'exploration d'un graphe consistant à visiter tous les sommets à un même niveau avant de passer au niveau suivant, en utilisant une structure de file d'attente.

• Coloriage des sommets : technique pour marquer l'état d'un sommet durant l'exploration, avec trois couleurs possibles :

  • Blanc : sommet non découvert,
  • Gris : sommet découvert mais dont tous les successeurs ne sont pas encore explorés,
  • Noir : sommet entièrement exploré.

• Liste d'attente : structure FIFO (First In First Out) utilisée pour gérer les sommets à explorer dans le parcours en largeur. Elle stocke les sommets gris à traiter.

• Arborescence de découverte : arbre ou graphe partiel constitué des arcs qui relient chaque sommet découvert à son prédécesseur lors du parcours, représentant la structure de l'exploration.

• Tableau des prédécesseurs : tableau où chaque élément indique le sommet qui a permis de découvrir le sommet correspondant lors du parcours, initialisé à -1 pour les sommets racines ou non encore découverts.

📝 Points essentiels

• Le parcours en largeur commence par un sommet initial, qui est mis dans la file d'attente, colorié en gris, et dont le prédécesseur est -1.
• À chaque étape, on retire le sommet en tête de la file, puis on explore ses successeurs.
• Si un successeur est blanc, il devient gris, son prédécesseur est mis à jour, et il est ajouté à la fin de la file.
• Une fois tous ses successeurs explorés, le sommet courant est colorié en noir.
• La structure de l'arborescence de découverte est construite à partir du tableau des prédécesseurs.
• La distance (niveau) d’un sommet par rapport au sommet de départ peut être stockée dans un tableau dédié, initialisé à -1, puis mise à jour lors de l'exploration.
• Le parcours garantit la visite de tous les sommets accessibles depuis le sommet initial dans l'ordre croissant de leur niveau.

💡 À retenir

Le parcours en largeur explore un graphe niveau par niveau en utilisant une file d'attente, permettant de déterminer la connectivité, les distances minimales, et de construire une arborescence de découverte.

📖 5. Parcours en profondeur

🔑 Notions clés & Définitions

• Parcours en profondeur (Depth First Search, DFS) : méthode d'exploration d'un graphe qui consiste à suivre un chemin le plus loin possible avant de revenir en arrière pour explorer d'autres branches. La gestion de la liste d'attente se fait comme une pile (LIFO).

• Pile (stack) : structure de données où le dernier élément ajouté est le premier à être retiré. Utilisée dans le parcours en profondeur pour gérer l'exploration des sommets.

• Exploration chemin le plus long : concept lié à la recherche du plus long chemin dans un graphe, souvent abordé en utilisant le parcours en profondeur pour explorer toutes les branches possibles.

📝 Points essentiels

• Le parcours en profondeur utilise une pile pour gérer la liste d'attente, ce qui permet d'explorer un chemin jusqu'à sa fin avant de revenir en arrière.
• La gestion des couleurs (blanc, gris, noir) permet de suivre l'état d'exploration des sommets : blanc (non découvert), gris (en cours d'exploration), noir (terminé).
• La variable dec enregistre la date de découverte d’un sommet, tandis que fin enregistre la date de fin de traitement.
• Lorsqu’un sommet est découvert, il est colorié en gris, puis ses successeurs sont explorés. Une fois tous ses successeurs traités, il est colorié en noir.
• La gestion de la date (tps) permet de suivre l’ordre d’exploration et de traitement des sommets.

💡 À retenir

Le parcours en profondeur explore un graphe en suivant un chemin jusqu’à sa fin avant de revenir en arrière, utilisant une pile pour gérer l’ordre d’exploration, ce qui permet de découvrir en profondeur chaque branche du graphe.

📖 6. Recherche de cycles

🔑 Notions clés & Définitions

• Cycle : Un cycle est une chaîne de sommets reliés deux à deux par des arêtes ou arcs, qui commence et se termine au même sommet, et dont tous les autres sommets sont distincts. Si une chaîne relie un sommet à lui-même, on parle aussi de cycle.

• Cycle dans un graphe : Un cycle est une séquence finie de sommets reliés par des arêtes ou arcs, formant une boucle fermée, sans répétition de sommets sauf le début et la fin.

• Cycle orienté : Un cycle dans un graphe orienté est une chaîne fermée où chaque arc est orienté dans le même sens que la chaîne, formant une boucle dans le sens de la direction des arcs.

• Cycle non orienté : Un cycle dans un graphe non orienté est une chaîne fermée où les arêtes n'ont pas de sens, formant une boucle sans orientation spécifique.

• Cycle simple : Un cycle qui ne passe pas deux fois par le même sommet, sauf le sommet de départ/fin.

• Cycle avec répétition : Un cycle qui peut passer plusieurs fois par certains sommets, c'est-à-dire pas nécessairement simple, pouvant contenir des répétitions de sommets ou d'arêtes.

📝 Points essentiels

• Lors du parcours en profondeur (DFS), si un successeur $s_j$ d’un sommet courant $s_i$ est déjà gris, cela indique l'existence d’un cycle, car cela signifie qu’il existe un chemin de $s_j$ vers $s_i$, formant une boucle.

• La détection de cycles dans un graphe orienté se fait en vérifiant si, lors du DFS, un successeur gris est rencontré. Si oui, le graphe contient un cycle.

• La détection de cycles dans un graphe non orienté repose aussi sur le DFS, mais en vérifiant si un successeur gris n’est pas le père dans l’arborescence, ce qui indique un cycle.

• La fonction pour tester si un graphe est acyclique retourne False si un cycle est détecté, et True sinon.

💡 À retenir

La présence d’un successeur déjà gris lors d’un parcours en profondeur indique un cycle dans le graphe, permettant de détecter si le graphe est acyclique ou non.

📊 Tableaux de Synthèse

Critère	Graphe non orienté	Graphe orienté	Auteur / Référence
Définition	Sommets reliés par des arêtes sans sens	Sommets reliés par des arcs avec sens	Notions clés & Définitions
Représentation	Matrice d’adjacence ou dictionnaire	Matrice d’adjacence ou dictionnaire	Représentation en Python
Sommet	Élément de V	Élément de V	Notions clés & Définitions
Arête / Arc	Paire {s, t}	Couple (s, t)	Notions clés & Définitions
Degré (d(s))	Somme des degrés (∑𝑠∈𝑉 𝑑(𝑠) = 2 *	𝐸	)
Parcours en largeur	Utilise une file, couleurs (blanc, gris, noir)	Même principe, avec gestion des successeurs	Parcours en largeur

⚠️ Pièges & Confusions Fréquentes

1. Confondre arête (non orienté) et arc (orienté) dans la représentation.
2. Oublier que la somme des degrés dans un graphe non orienté est égale à 2 fois le nombre d’arêtes.
3. Confondre liste des voisins et liste des successeurs dans la représentation Python.
4. Négliger la différence entre degré entrant et degré sortant dans un graphe orienté.
5. Utiliser une représentation matricielle pour un graphe très dense sans optimiser la mémoire.
6. Confondre sommet non découvert (blanc) et sommet en cours d’exploration (gris) lors du parcours en largeur.
7. Omettre de marquer un sommet comme entièrement exploré (noir) pour éviter des visites infinies.

✅ Checklist Examen

1. Connaître la définition d’un graphe non orienté et orienté, et leur différence.
2. Savoir représenter un graphe en Python via une matrice d’adjacence.
3. Savoir représenter un graphe en Python via un dictionnaire d’adjacence.
4. Comprendre la notion de sommet, arête, arc, degré entrant et degré sortant.
5. Maîtriser la procédure du parcours en largeur, y compris la gestion des couleurs.
6. Savoir comment construire l’arborescence de découverte lors d’un parcours en largeur.
7. Connaître la différence entre parcours en largeur et parcours en profondeur.
8. Comprendre la notion de cycle dans un graphe orienté et non orienté.
9. Être capable de détecter un cycle à partir d’un parcours en largeur ou profondeur.
10. Connaître la définition et l’utilité d’un graphe de dépendances.
11. Maîtriser la modélisation d’un labyrinthe ou d’un réseau social par un graphe.
12. Savoir utiliser la structure de données Python adaptée pour représenter un graphe selon le contexte.