Fiche de révision : Introduction à la théorie des graphes

📋 Plan du Cours

1. Définitions des graphes non orientés
2. Sous-graphes degrés et chemins
3. Graphes eulériens et hamiltoniens
4. Couplages et graphes planaires
5. Représentations et arbres
6. Arbres couvrants minimaux
7. Coloration des graphes
8. Coloration avancée des graphes
9. Graphes triangulés
10. Fondements des graphes orientés
11. Chemins et connexité orientée
12. Représentations et ordonnancement
13. Plus courts chemins
14. Réseaux PERT et chemin critique

📖 1. Définitions des graphes non orientés

🔑 Notions clés & Définitions

• Graphe fini : Défini par un ensemble fini V de sommets et un ensemble fini E d’arêtes, chaque arête étant une paire non ordonnée de sommets appelés ses extrémités.
• Graphe simple : Possède au plus une arête entre deux sommets et ne contient aucune boucle.
• Graphe connexe : S’il est possible, à partir de n’importe quel sommet, de rejoindre tous les autres en suivant les arêtes.
• Graphe biparti : Ses sommets peuvent être divisés en deux ensembles X et Y de sorte que chaque arête relie un sommet de X à un sommet de Y.
• Graphe d’intervalles : Les sommets représentent des intervalles de la droite réelle et deux sommets sont reliés si et seulement si les intervalles correspondants se chevauchent.

💡 Astuce mémo

Simple = une arête au plus et aucune boucle ; multigraphe = boucles ou arêtes multiples.

📖 2. Sous-graphes degrés et chemins

🔑 Notions clés & Définitions

• Degré d’un sommet : Le nombre d’arêtes incidentes à ce sommet, une boucle comptant double.
• Chaîne : Une suite alternée de sommets et d’arêtes, commençant et se terminant par un sommet, chaque arête étant encadrée par ses extrémités.

★ À maîtriser

• La somme des degrés des sommets d’un graphe est égale à $2m$, où m est le nombre d’arêtes.

📌 Une chaîne est élémentaire si chaque sommet y apparaît au plus une fois, simple si chaque arête y apparaît au plus une fois, et un cycle si elle est fermée et simple.

Compléments

📐 Formule — Pour un graphe ayant m arêtes, n sommets et p composantes connexes, le nombre cyclomatique vaut $\nu(G)=m-n+p$ et il est nul si et seulement si le graphe est sans cycle.

💡 Astuce mémo

Les arêtes incidentes déterminent les degrés, qui structurent ensuite chaînes, cycles et connexité.

📖 3. Graphes eulériens et hamiltoniens

🔑 Notions clés & Définitions

• Graphe eulérien : S’il possède un cycle passant une et une seule fois par chacune de ses arêtes.
• Graphe hamiltonien : S’il possède un cycle passant une et une seule fois par chacun de ses sommets.

★ À maîtriser

📌 D’après le théorème d’Ore, un graphe simple d’ordre n>3 est hamiltonien si, pour toute paire de sommets non adjacents x et y, on a d(x)+d(y)>n.

Compléments

📌 Un graphe possédant un sommet de degré 1 ne peut pas être hamiltonien, et si un sommet a le degré 2, ses deux arêtes incidentes doivent appartenir au cycle hamiltonien.

💡 Astuce mémo

Eulérien parcourt chaque arête une fois ; hamiltonien parcourt chaque sommet une fois.

📖 4. Couplages et graphes planaires

🔑 Notions clés & Définitions

• Couplage : Un ensemble d’arêtes deux à deux non adjacentes, ou de manière équivalente un sous-graphe partiel 1-régulier.

📝 Points essentiels

📌 Un couplage maximum contient le plus grand nombre possible d’arêtes, tandis qu’un couplage parfait sature tous les sommets du graphe.

📌 D’après le théorème de Berge (1957), un couplage C est maximum si et seulement s’il n’existe aucune chaîne augmentante relativement à C.

📐 Formule — Pour une carte connexe, si S est le nombre de sommets, A le nombre d’arêtes et R le nombre de régions, la formule d’Euler est $S-A+R=2$.

💡 Astuce mémo

Un couplage associe des arêtes disjointes ; la planarité interdit les croisements d’arêtes.

📖 5. Représentations et arbres

🔑 Notions clés & Définitions

• Arbre : Un graphe connexe sans cycle.

★ À maîtriser

📌 Pour un graphe à n sommets, les propriétés être un arbre, être connexe avec n−1 arêtes, et relier chaque paire de sommets par une unique chaîne simple sont équivalentes.

• Le codage de Prüfer d’un arbre à n sommets est une suite de n−2 termes obtenue en supprimant successivement la feuille de plus petit numéro et en ajoutant son voisin à la suite.

Compléments

• Tout arbre fini comportant au moins deux sommets possède au moins deux sommets pendants, c’est-à-dire des sommets de degré 1.

• Le nombre d’arbres construits sur n sommets numérotés, avec n≥2, est égal à $n^{n-2}$. — Cayley, 1857

💡 Astuce mémo

Matrice ou listes → arbre → codage de Prüfer.

📖 6. Arbres couvrants minimaux

🔑 Notions clés & Définitions

• Arbre couvrant : Un graphe partiel qui contient tous les sommets du graphe et qui est lui-même un arbre.

📝 Points essentiels

• L’algorithme de Kruskal construit un arbre couvrant de poids minimum en triant les arêtes par poids croissant et en ajoutant chaque arête qui ne forme pas de cycle, jusqu’à obtenir n−1 arêtes.

💡 Astuce mémo

Kruskal : trier les poids, ajouter sans former de cycle, arrêter à n−1 arêtes.

📖 7. Coloration des graphes

🔑 Notions clés & Définitions

• Coloration des sommets : Affecte une couleur à chaque sommet de sorte que deux sommets adjacents aient des couleurs différentes.
• Nombre chromatique : Le plus petit nombre de couleurs permettant de partitionner les sommets d’un graphe en stables.

★ À maîtriser

📐 Formule — Si r est le degré maximum d’un graphe, son nombre chromatique vérifie $\gamma(G)\le r+1$, et si α(G) est le nombre de stabilité, il vérifie aussi $\gamma(G)\le n+1-\alpha(G)$.

📐 Formule — Le nombre chromatique d’un graphe est au moins égal à la taille de sa plus grande clique, soit $\gamma(G)\ge\omega(G)$.

📌 Tout graphe planaire sans boucles peut être coloré avec au plus quatre couleurs de sorte que deux sommets reliés par une arête aient des couleurs différentes. — Kenneth Appel et Wolfgang Haken, 1976

Compléments

• L’algorithme de Welsh et Powell classe les sommets par degrés décroissants, puis attribue successivement une couleur à un sommet non coloré et à chaque sommet non adjacent à ceux déjà coloriés avec cette couleur.

💡 Astuce mémo

Une coloration sépare les sommets adjacents ; le nombre chromatique cherche le minimum de couleurs.

📖 8. Coloration avancée des graphes

🔑 Notions clés & Définitions

• Graphe parfait : Claude Berge, 1960 — Graphe tel que, pour tout sous-graphe induit G′, son nombre chromatique γ(G′) est égal à la taille ω(G′) de sa plus grande clique.
• Indice chromatique : Plus petit nombre de couleurs permettant de colorer les arêtes d’un graphe de sorte que deux arêtes adjacentes n’aient pas la même couleur.

📝 Points essentiels

• L’algorithme de Welsh et Powell classe les sommets par degré décroissant, attribue une nouvelle couleur au premier sommet non coloré, puis donne cette couleur aux sommets non colorés qui ne sont adjacents à aucun sommet déjà coloré avec elle, jusqu’à coloration complète.

📌 Le théorème des quatre couleurs affirme que les sommets de tout graphe planaire sans boucles peuvent être colorés avec au plus quatre couleurs de manière que les extrémités de chaque arête aient des couleurs différentes. — Kenneth Appel et Wolfgang Haken, 1976

💡 Astuce mémo

Welsh-Powell colore bien, mais pas forcément au minimum

📖 9. Graphes triangulés

🔑 Notions clés & Définitions

• Graphe triangulé : Graphe dont chacun des cycles de plus de trois sommets contient au moins une corde reliant deux sommets non adjacents du cycle.
• Sommet simplicial : Un sommet v est simplicial lorsque son voisinage N(v) est une clique.

📝 Points essentiels

📌 Un graphe connexe est triangulé si et seulement si tout séparateur minimal est une clique.

• L’algorithme de Fulkerson et Gross reconnaît un graphe triangulé en supprimant successivement un sommet simplicial ; si le graphe résiduel devient vide, le graphe est triangulé, et s’il reste un graphe sans sommet simplicial, il ne l’est pas.

💡 Astuce mémo

Élimination de sommets simpliciaux → reconnaissance et coloration

📖 10. Fondements des graphes orientés

🔑 Notions clés & Définitions

• Digraphe : Graphe fini défini par un ensemble fini de sommets V et un ensemble fini d’arcs E, chaque arc étant une paire ordonnée de sommets.
• Degré orienté : Dans un digraphe, le degré extérieur d⁺(v) compte les arcs dont v est l’extrémité initiale, le degré intérieur d⁻(v) compte les arcs dont v est l’extrémité finale, et le degré total vérifie $d(v)=d^+(v)+d^-(v)$.
• Chemin orienté : Suite alternée de sommets et d’arcs commençant et se terminant par un sommet, chaque arc allant de son sommet origine vers son sommet destination.
• Distance orientée : La distance d(x,y) entre deux sommets d’un digraphe est la longueur du plus court chemin de x vers y, et elle vaut ∞ lorsqu’aucun chemin de x vers y n’existe.

💡 Astuce mémo

Un arc distingue une extrémité initiale d’une extrémité finale

📖 11. Chemins et connexité orientée

🔑 Notions clés & Définitions

• Circuit : Chemin dont le sommet de départ et le sommet de fin coïncident.
• Digraphe fortement connexe : Digraphe dans lequel toute paire ordonnée de sommets distincts est reliée par au moins un chemin.
• Composante fortement connexe : Sous-graphe induit maximal fortement connexe.

📝 Points essentiels

• Un tournoi est un digraphe complet et tout tournoi admet un chemin hamiltonien. — Landau, 1953

💡 Astuce mémo

Chemin orienté ≠ chaîne non orientée : on ne remonte pas les arcs

📖 12. Représentations et ordonnancement

🔑 Notions clés & Définitions

• Matrice d’adjacences : Matrice carrée dont l’entrée (i,j) vaut 1 lorsqu’un arc va de i vers j et 0 sinon.
• Graphe de comparabilité : Graphe dont les arêtes peuvent être orientées transitivement, c’est-à-dire que les arcs i vers j et j vers k entraînent l’existence de l’arc i vers k.

★ À maîtriser

📌 Un digraphe est sans circuit si et seulement s’il existe un rang r(v) pour chaque sommet tel que tout arc (u,v) vérifie r(u)<r(v).

Compléments

• Dans une matrice d’adjacences d’un digraphe simple, la diagonale ne contient que des zéros, car un 1 diagonal représenterait une boucle.

💡 Astuce mémo

Matrice → listes → rangs → orientation transitive

📖 13. Plus courts chemins

🔑 Notions clés & Définitions

• Algorithme de Dijkstra : Edgser Wybe Dijkstra, 1959 — L’algorithme de Dijkstra calcule les plus courts chemins depuis un sommet donné vers tous les autres dans un graphe pondéré dont les poids d’arcs sont positifs.

★ À maîtriser

• Dijkstra initialise les distances depuis le sommet de départ, choisit à chaque étape dans l’ensemble non traité le sommet de plus petite distance, puis améliore les distances de ses successeurs par relaxation jusqu’à traitement de tous les sommets.

Compléments

• Dans l’exemple fourni, les distances minimales depuis le sommet 1 sont λ=(0,12,11,9,4), et le plus court chemin de 1 à 4 est 1–5–4, de coût 9.

💡 Astuce mémo

Choisir le minimum, fixer son coût, relaxer ses successeurs

📖 14. Réseaux PERT et chemin critique

🔑 Notions clés & Définitions

• Réseau PERT : Réseau dans lequel chaque tâche est représentée par un arc pondéré par sa durée, les sommets représentent des événements et les arcs indiquent les précédences entre tâches.
• Chemin critique : Un chemin critique est un chemin de 1 à n composé uniquement d’arcs critiques, et tout retard d’une activité critique retarde la fin du projet.

📝 Points essentiels

📌 L’absence de circuit dans le réseau PERT garantit la faisabilité du projet, car un circuit imposerait qu’une tâche précède et suive simultanément une autre tâche.

📐 Formule — Les dates de début au plus tôt se calculent par $\delta_1=0$ puis $\delta_k=\max\{\delta_j+d_{jk}\mid j\in P(k)\}$ pour k de 2 à n.

📐 Formule — Les dates de fin au plus tard se calculent par $\varphi_n=\delta_n$ puis $\varphi_k=\min\{\varphi_j-d_{kj}\mid j\in S(k)\}$ en remontant de n−1 à 1.

💡 Astuce mémo

Précédences + durées → dates au plus tôt et au plus tard → chemin critique

📊 Tableaux de synthèse

Parcours des graphes

Coloration des graphes