Aide-mémoire Graphes

Les définitions, les théorèmes de base et les algorithmes du parcours Graphes, rangés pour être retrouvés vite. Les démonstrations et les figures qui se déroulent sont dans les chapitres ; ici, seulement ce qu'il faut avoir en tête.

Les mots

Terme	Définition
Graphe $G = (V, E)$	$n$ sommets $V$ et $m$ arêtes $E$ , des paires de sommets. Simple : ni boucle, ni arête multiple.
Orienté	Les arêtes ont un sens : ce sont des arcs $u \to v$ .
Pondéré	Chaque arête porte un poids : distance, coût, durée, capacité.
Voisins	Deux sommets reliés par une arête (adjacents).
Degré $\deg(v)$	Nombre d'arêtes qui touchent $v$ . En orienté : $\deg^+(v)$ arcs sortants, $\deg^-(v)$ entrants.
Chemin	Sommets reliés deux à deux par des arêtes (des arcs dans le bon sens, en orienté). Longueur : nombre d'arêtes ; poids : somme de leurs poids.
Cycle, circuit	Chemin fermé qui ne repasse par aucune arête ; on dit circuit en orienté.
Distance $\mathrm{dist}(u, v)$	Longueur, ou poids, d'un plus court chemin de $u$ à $v$ .
Connexe	Un chemin relie toute paire de sommets ; les morceaux sont les composantes connexes.
Fortement connexe	En orienté : un chemin de $u$ à $v$ et de $v$ à $u$ , pour toute paire.
Sous-graphe induit	Des sommets choisis, et toutes les arêtes qui les relient.
Clique	Sommets deux à deux voisins ; $\omega(G)$ est la taille de la plus grande.

Les familles à reconnaître

Famille	Définition, et ce qu'il faut savoir
Complet $K_n$	Toutes les paires reliées ; $m = n(n-1)/2$ .
Cycle $C_n$	$n \geq 3$ sommets en boucle ; biparti si $n$ est pair ; $\chi(C_5) = 3$ sans aucun triangle.
Biparti	Deux camps, arêtes entre camps seulement. Biparti $\iff$ aucun cycle de longueur impaire $\iff$ $\chi \leq 2$ .
Arbre	Connexe et sans cycle ; $m = n - 1$  ; un seul chemin entre deux sommets. Forêt : sans cycle.
DAG	Orienté sans circuit ; admet un tri topologique, a une source et un puits.
Planaire	Se dessine sans croisement. $m \leq 3n - 6$  ; $K_5$ et $K_{3,3}$ ne le sont pas.
Eulérien	Un cycle passe une fois par chaque arête : voir le théorème d'Euler.
Hamiltonien	Un cycle passe une fois par chaque sommet : aucun critère simple, problème difficile (NP-complet).
D'intervalles	Un sommet par intervalle, une arête s'ils se chevauchent ; le glouton par début croissant est optimal, $\chi = \omega$ .

Les théorèmes de base

Théorème	Énoncé, et ce qu'il permet
Poignées de main	$\sum_v \deg(v) = 2m$  : on en tire $m$ , et le nombre de sommets de degré impair est pair. En orienté, $\sum \deg^+ = \sum \deg^- = m$ .
Arbres	Pour $n$ sommets, deux propriétés parmi « connexe », « sans cycle » et «  $m = n - 1$  » entraînent la troisième. Ajouter une arête à un arbre crée exactement un cycle.
Bipartis	Biparti $\iff$ aucun cycle impair : un cycle impair prouve qu'un graphe n'est pas biparti.
Euler (tournées)	Arêtes d'un seul tenant : cycle eulérien $\iff$ degrés tous pairs ; chemin eulérien $\iff$ 0 ou 2 degrés impairs. Königsberg : quatre impairs, aucune promenade.
Euler (faces)	Planaire connexe : $n - m + f = 2$ , d'où $m \leq 3n - 6$ .
Tri topologique	Il existe $\iff$ le graphe n'a pas de circuit. Un circuit est une contradiction dans les contraintes.
Encadrement de $\chi$	$\omega(G) \leq \chi(G) \leq \Delta(G) + 1$ , où $\Delta$ est le degré maximal. Une coloration à $k$ couleurs prouve $\chi \leq k$ , jamais $\chi = k$ .
Quatre couleurs	Tout graphe planaire vérifie $\chi \leq 4$ .
Propriété de coupe	L'arête la plus légère qui traverse une coupe appartient à un arbre couvrant minimal ; arbre unique si les poids sont distincts. Elle justifie Kruskal et Prim.
Flot max, coupe min	La valeur d'un flot maximal égale la capacité d'une coupe minimale : une coupe de même valeur certifie le flot.
Chemin augmentant	Un flot, ou un couplage, est maximum $\iff$ il n'admet aucun chemin augmentant : c'est le critère d'arrêt.
Hall	Un biparti $(X, Y)$ a un couplage qui sature $X$ $\iff$ $\lvert N(W) \rvert \geq \lvert W \rvert$ pour tout $W \subseteq X$  : deux candidats pour un seul poste suffisent à prouver l'impossibilité.

Représenter en machine

Représentation	Mémoire, et coût des deux questions « voisins de $u$  ? » et «  $u$ et $v$ voisins ? »
Matrice d'adjacence	$O(n^2)$  ; voisins en $O(n)$  ; test en $O(1)$ . À réserver aux petits graphes denses.
Liste d'adjacence	$O(n + m)$  ; voisins en $O(\deg u)$  ; test en $O(\deg u)$ . En Python `{u: [voisins]}`, pondéré `{u: {v: poids}}`.
Liste d'arêtes	$O(m)$  ; tout se fait en $O(m)$ . Le format d'entrée de Kruskal.
Puissances $A^k$	Le coefficient $(i, j)$ compte les chemins de longueur $k$ de $i$ à $j$ , arêtes répétées permises ; la diagonale de $A^2$ donne les degrés.
Graphe creux	$m \ll n^2$  : liste d'adjacence. Une matrice de 200 000 carrefours a $4 \times 10^{10}$ cases, presque toutes vides.

Les algorithmes

Algorithme	Ce qu'il calcule, sa condition, son coût, son idée
Parcours en largeur	Sommets atteignables et distances en nombre d'arêtes ; $O(n + m)$ . Une file ; marquer à l'entrée dans la file.
Parcours en profondeur	Composantes, cycles, ordre de fin ; $O(n + m)$ . Une pile ou la récursion ; marquer à la sortie de la pile.
Dijkstra	Plus courts chemins depuis une source, poids $\geq 0$  ; $O((n + m) \log n)$ . Glouton : figer le sommet le plus proche, relâcher ses arcs.
Bellman-Ford	Plus courts chemins avec poids négatifs, sans circuit négatif ; $O(nm)$ . $n - 1$ passes de relâchement, puis une passe de contrôle.
Kruskal	Arbre couvrant minimal ; $O(m \log m)$ . Arêtes par poids croissant, rejeter celles qui ferment un cycle (union-trouve).
Prim	Arbre couvrant minimal ; $O(m \log n)$ . Faire grossir un seul arbre par l'arête la plus légère qui en sort.
Kahn	Tri topologique d'un DAG ; $O(n + m)$ . Retirer les sommets sans prédécesseur ; s'il en reste, il y a un circuit.
Kosaraju, Tarjan	Composantes fortement connexes ; $O(n + m)$ . Un ou deux parcours en profondeur, guidés par l'ordre de fin.
Coloration gloutonne	Chaque sommet prend la plus petite couleur libre ; au plus $\Delta + 1$ couleurs, et l'ordre décide du résultat.
Edmonds-Karp	Flot maximal ; $O(nm^2)$ . Chemins augmentants les plus courts dans le graphe résiduel, arcs inverses compris.

Modéliser un problème

Problème réel	Le graphe, puis l'outil
Itinéraire le plus rapide	Carrefours et tronçons pondérés par le temps : Dijkstra.
Relier des sites au moindre coût	Sites et liaisons possibles avec leur coût : arbre couvrant minimal.
Planifier des tâches	DAG des précédences et durées : tri topologique, chemin critique.
Créneaux sans conflit	Un sommet par activité, une arête par conflit : coloration (salles, fréquences, horaires).
Affecter des personnes	Biparti candidats et postes : couplage maximum.
Débit d'un réseau	Réseau orienté avec capacités : flot maximal, et la coupe minimale désigne le goulot.
Chaque rue une fois	Les rues sont les arêtes : graphe eulérien.
Chaque ville une fois	Les villes sont les sommets : hamiltonien, difficile, on se contente d'heuristiques.
Date au plus tôt	$\mathrm{tôt}(v) = \max_{u \to v} \big(\mathrm{tôt}(u) + \mathrm{durée}(u)\big)$  ; durée du projet = plus long chemin.
Date au plus tard	$\mathrm{tard}(v) = \min_{v \to w} \mathrm{tard}(w) - \mathrm{durée}(v)$ .
Marge totale	$\mathrm{tard}(v) - \mathrm{tôt}(v)$  ; la tâche est critique si elle est nulle.

Les pièges

Piège	Ce qui est vrai
Poids négatif	Dijkstra peut rendre un résultat faux : Bellman-Ford.
«  $k$ couleurs, donc $\chi = k$  »	Seulement $\chi \leq k$ . Minorer demande une clique, un cycle impair ou un raisonnement.
« Pas de triangle, donc 2 couleurs »	$C_5$ n'a aucun triangle et demande 3 couleurs.
Glouton de coloration	Il dépend de l'ordre ; optimal dans quelques cas seulement (intervalles par début croissant).
Preuve de non-bipartisme	Seul un cycle impair prouve ; une arête entre deux sommets de même couleur peut venir d'un mauvais choix.
Profondeur	Ce n'est pas la largeur avec une pile : la marque change de place.
Durée d'un projet	Pas la somme des durées : le plus long chemin du DAG.
Deux arbres	L'arbre couvrant minimal n'est pas l'arbre des plus courts chemins : deux questions différentes.
Flot bloqué	Plus de chemin de $s$ à $t$ dans le réseau ne prouve rien : chercher dans le graphe résiduel.
Grand graphe creux	Pas de matrice : la mémoire croît en $n^2$ .

Pour aller plus loin

Chaque ligne de cette page est démontrée et manipulée dans le parcours : le vocabulaire, les représentations, les parcours, les arbres couvrants, les plus courts chemins, les graphes orientés et l'ordonnancement, la coloration, les familles remarquables et les flots et couplages.

Version imprimable : les tables de syntaxe seules, sur une feuille.

Les autres aide-mémoire sont sur cette page, et les exercices dans Pratiquer.