Lernzettel: Introduction aux graphes et parcours efficaces

📋 Plan du Cours

1. Définitions fondamentales des graphes, graphes orientés et non orientés
2. Concepts de voisinage, degré, chemin, cycle, distance et connexité dans les graphes
3. Représentations des graphes en Python : matrices et listes d'adjacence
4. Modélisation des graphes avec dictionnaires et listes d'arêtes
5. Principes généraux des parcours de graphes et gestion des ensembles de sommets
6. Parcours en largeur (BFS) dans les graphes
7. Parcours en profondeur (DFS) dans les graphes
8. Recherche du plus court chemin et algorithme de Dijkstra sur graphes pondérés

📖 1. Définitions fondamentales des graphes, graphes orientés et non orientés

🔑 Notions clés & Définitions

• Graphe : Une structure composée d'un ensemble de sommets reliés par des arêtes, où seule la relation entre les sommets importe, indépendamment de leur disposition spatiale.

📝 Points essentiels

• Un graphe est un ensemble de sommets reliés par des arêtes, sans importance de disposition spatiale.
• Dans un graphe orienté, les liens sont appelés arcs et ont un sens unique.
• Dans un graphe non orienté, deux sommets sont adjacents s'ils sont reliés par une arête sans orientation.
• La disposition spatiale des sommets n'a pas d'importance, seul le lien entre sommets compte.
• Orienté / Non orienté Lorsque les sommets sont reliés dans un seul sens, on dit que le graphe est orienté, et les liens sont appelés arcs. Dans un graphe non orienté, on dit que deux sommets sont adjacents s'ils sont reliés par une arête.

💡 À retenir

Les graphes sont des ensembles de sommets reliés par des arêtes ou arcs, avec une distinction essentielle entre graphes orientés et non orientés basée sur la direction des liens.

📖 2. Concepts de voisinage, degré, chemin, cycle, distance et connexité dans les graphes

🔑 Notions clés & Définitions

• Voisinage : En théorie des graphes, le voisinage d'un sommet est l'ensemble des sommets qui lui sont directement reliés par une arête.
• Degré : Le degré d'un sommet correspond au nombre total de sommets adjacents à ce sommet ; dans un graphe orienté, le degré entrant compte les arcs arrivant au sommet, tandis que le degré sortant compte les arcs partant de ce sommet.
• Chemin : Un chemin est une séquence ordonnée de sommets telle que chaque paire consécutive est reliée par une arête ou un arc ; un chemin est simple s'il ne traverse aucune arête ou arc plus d'une fois.

📝 Points essentiels

• Deux sommets reliés par une arête sont voisins.
• La distance entre deux sommets est la longueur du plus court chemin entre eux, mesurée en nombre d'arêtes ou en somme des poids si pondéré.
• Chemin Un chemin dans un graphe est une suite de noeuds possible en suivant les arêtes ou les arcs du graphe. Exemple : Il existe un chemin reliant 5 à 1 qui est 5 - 4 - 6 - 1 Un chemin est dit simple s'il ne passe pas deux fois par la même arête ou le même arc.

💡 À retenir

La distance entre deux sommets est la longueur du plus court chemin entre eux, mesurée en nombre d'arêtes ou en somme des poids si pondéré.

📖 3. Représentations des graphes en Python : matrices et listes d'adjacence

🔑 Notions clés & Définitions

• Matrice d'adjacence : Structure de données sous forme de tableau à deux dimensions (liste de listes en Python) où le nombre de lignes et de colonnes correspond au nombre de sommets du graphe, chaque case valant 0 ou 1 selon l'absence ou la présence d'une arête entre les sommets.
• Liste d'adjacence : Structure de données constituée d'une liste contenant autant de sous-listes qu'il y a de sommets, chaque sous-liste énumérant les sommets voisins du sommet correspondant, avec une numérotation des sommets généralement décalée pour commencer à 0.

📝 Points essentiels

• La matrice d'adjacence est une liste de listes carrée indiquant la présence (1) ou l'absence (0) d'arêtes entre sommets.
• La matrice peut aussi contenir le nombre d'arêtes ou le poids des arêtes en variante.
• La liste d'adjacence est une liste où chaque élément est une sous-liste des sommets voisins du sommet correspondant.
• La numérotation des sommets dans la liste d'adjacence commence généralement à 0 pour correspondre aux indices.
• Matrice d'adjacence On utilise une matrice (comprenez un tableau à deux dimensions) pour représenter les liaisons entre les sommets du graphe. On utilise une liste de listes en Python.
• Listes d'adjacence La liste d'adjacence d'une matrice indique pour chaque sommet avec quel autre sommet il est relié.

💡 À retenir

Savoir représenter efficacement un graphe en Python via deux structures fondamentales adaptées à différents besoins.

📖 4. Modélisation des graphes avec dictionnaires et listes d'arêtes

🔑 Notions clés & Définitions

• Dictionnaire : Structure permettant de conserver les libellés des sommets tout en listant leurs voisins, facilitant la manipulation de graphes avec des sommets non numériques ou non contigus.

📝 Points essentiels

• La liste d'arêtes est particulièrement adaptée à certains algorithmes comme Bellman-Ford.
• Le dictionnaire permet de conserver les libellés des sommets tout en listant leurs voisins.

💡 À retenir

Utiliser des structures flexibles pour modéliser des graphes avec des sommets étiquetés ou pour certains algorithmes spécifiques.

📖 5. Principes généraux des parcours de graphes et gestion des ensembles de sommets

🔑 Notions clés & Définitions

• La coupe : L'ensemble de sommet connus mais non encore visités
• Sommets non encore rencontrés : Ce sont les sommets du graphe qui n'ont pas encore été découverts ou inclus dans aucun des ensembles de parcours.

📝 Points essentiels

• Le parcours d'un graphe nécessite un sommet de départ.
• Les sommets sont divisés en trois ensembles : visités, coupe, non rencontrés.
• La gestion de la coupe est centrale pour contrôler le déroulement du parcours.

💡 À retenir

Comprendre la structure commune à tous les parcours de graphes via la gestion dynamique des ensembles de sommets.

📖 6. Parcours en largeur (BFS) dans les graphes

🔑 Notions clés & Définitions

• Parcours en largeur (BFS) : Le parcours en largeur explore d'abord tous les sommets à distance 1 du départ, puis ceux à distance 2, etc., en utilisant une file pour gérer la coupe.

📝 Points essentiels

• La coupe est gérée comme une file : le premier sommet ajouté est le premier visité.
• Le parcours BFS n'est pas unique, plusieurs ordres de visite sont possibles.
• Le BFS est similaire au parcours en largeur des arbres.

💡 À retenir

Appréhender le BFS comme un parcours ordonné par la distance croissante au sommet de départ, géré par une file.

📖 7. Parcours en profondeur (DFS) dans les graphes

🔑 Notions clés & Définitions

• Parcours en profondeur (DFS) : Le parcours en profondeur explore un graphe en allant aussi loin que possible le long d'un chemin avant de revenir en arrière, en utilisant une structure de pile pour gérer la coupe.

📝 Points essentiels

• La coupe est gérée comme une pile : le dernier sommet ajouté est le premier visité.
• Le DFS est analogue au parcours préfixe des arbres.

💡 À retenir

Visualiser le DFS comme un parcours qui plonge au maximum dans le graphe, contrôlé par une pile.

📖 8. Recherche du plus court chemin et algorithme de Dijkstra sur graphes pondérés

🔑 Notions clés & Définitions

• Itération : Une étape répétée dans l'exécution d'un algorithme au cours de laquelle une sélection et une mise à jour des données sont effectuées.
• Plus court chemin : Un chemin entre deux sommets d'un graphe qui minimise la somme des poids des arcs empruntés.

📝 Points essentiels

• La recherche du plus court chemin s'applique souvent sur des graphes orientés pondérés mais l'algorithme est général.
• L'algorithme de Dijkstra initialise les distances à l'infini sauf pour le sommet de départ à zéro.
• À chaque itération, Dijkstra choisit le sommet non inclus au sous-graphe avec la distance minimale et met à jour les distances de ses voisins.
• L'algorithme s'arrête lorsque le sommet d'arrivée est inclus ou que tous les sommets ont été traités.
• Quels graphes La majorité du temps, la recherche du plus court chemin entre deux sommets se réalise sur un graphe orienté pondéré. Dans les autres cas cependant, l'algorithme restera toujours le même !

💡 À retenir

L'algorithme de Dijkstra exploite de manière itérative les distances minimales pour construire efficacement le plus court chemin entre deux sommets dans un graphe pondéré.

📊 Tableaux de Synthèse

Comparaison des représentations de graphes en Python

Type de structure	Avantages	Inconvénients
Matrice d'adjacence	Facile à implémenter, efficace pour graphes denses	Consomme beaucoup de mémoire pour graphes clairsemés, difficile à manipuler pour de grands graphes
Liste d'adjacence	Efficace pour graphes clairsemés, facile à parcourir	Moins efficace pour vérifier la présence d'une arête entre deux sommets

Parcours de graphes : BFS vs DFS

Critère	BFS	DFS
Type de parcours	Exploration par niveaux	Exploration en profondeur
Structure de gestion	File (queue)	Pile (stack)
Application typique	Recherche du plus court chemin dans un graphe non pondéré	Exploration exhaustive, détection de cycles

⚠️ Pièges & Confusions Fréquentes

1. Confondre graphes orientés et non orientés lors de la modélisation.
2. Utiliser la mauvaise représentation (matrice ou liste) selon la densité du graphe.
3. Oublier de gérer la mémoire lors de l'utilisation de matrices pour de grands graphes.
4. Confondre la gestion de la coupe dans BFS et DFS, menant à des parcours incorrects.
5. Ne pas mettre à jour correctement les distances dans l'algorithme de Dijkstra.
6. Supposer que tous les graphes pondérés ont des poids positifs, ce qui n'est pas toujours le cas.
7. Confondre chemin simple et chemin avec cycles dans la définition.

✅ Checklist Examen

1. Vérifier la distinction entre graphes orientés et non orientés.
2. Savoir choisir entre matrice et liste d'adjacence selon le contexte.
3. Comprendre la logique de l'algorithme de Dijkstra.
4. Savoir représenter un graphe avec dictionnaires ou listes d'arêtes.
5. Identifier la différence entre voisinage, degré, chemin, cycle.
6. Calculer la distance minimale entre deux sommets.
7. Utiliser efficacement les structures de données pour le parcours.
8. Reconnaître les situations où utiliser un algorithme spécifique.
9. Gérer les cas de graphes pondérés avec poids négatifs.