Le modèle des graphes

Cours complet · informatique (MP2I/MPI), chapitre 13 · MP2I et MPI

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

13.1 Un modèle, et presque tout devient un graphe

Le programme range les graphes parmi les « structures de données relationnelles », et le mot est juste : là où l'arbre impose une hiérarchie, le graphe ne dit rien de plus que « ces objets sont reliés ». C'est cette pauvreté qui fait sa portée.

Il demande de « mettre en avant des applications importantes et si possible modernes : réseau de transport, graphe du web, réseaux sociaux, bio-informatique », et de « préciser autant que possible la taille typique de tels graphes ». Ces ordres de grandeur ne sont pas anecdotiques — ils décident de l'algorithme qu'on a le droit d'écrire.

Graphe	Sommets	Arcs	Ce qu'un $O (n^{2})$ donnerait
Métro d'une ville	$\sim 300$	$\sim 700$	instantané
Réseau routier français	$\sim 1 0^{7}$	$\sim 2 \cdot 1 0^{7}$	$1 0^{14}$ opérations : des jours
Graphe du web	$> 1 0^{11}$	$> 1 0^{12}$	inconcevable
Réseau social mondial	$\sim 3 \cdot 1 0^{9}$	$\sim 5 \cdot 1 0^{11}$	inconcevable

ImportantLa leçon de ce tableau

Sur un graphe de $1 0^{7}$ sommets, un algorithme en $O (n^{2})$ est inutilisable, et un algorithme en $O (n + m)$ tourne en quelques secondes. C'est pourquoi la représentation choisie — matrice ou listes — n'est pas un détail d'écriture : elle change la complexité de tout ce qu'on bâtira dessus.

13.2 Définitions

Définition 13.1Graphe orienté, graphe non orienté

Un graphe $G = (S, A)$ est la donnée d'un ensemble fini $S$ de sommets (ou nœuds) et d'un ensemble $A$ de liens.

Si les liens sont des couples $(u, v)$ ordonnés, on parle d'arcs et le graphe est orienté.
Si ce sont des paires ${u, v}$ non ordonnées, on parle d'arêtes et le graphe est non orienté.

On note $n = ∣ S ∣$ et $m = ∣ A ∣$ . Une boucle est un arc ou une arête d'un sommet vers lui-même. Le programme précise : « on n'évoque pas les multi-arcs » — entre deux sommets, il y a au plus un lien dans chaque sens.

Définition 13.2Degrés

Dans un graphe non orienté, le degré $d (s)$ est le nombre d'arêtes incidentes à $s$ . Dans un graphe orienté, le programme fixe les notations :

$d^{+} (s) = nombre d’arcs sortant de s, d^{-} (s) = nombre d’arcs entrant en s .$

Proposition 13.3Lemme des poignées de main

Dans un graphe non orienté, $s \in S \sum d (s) = 2 m$ . Dans un graphe orienté, $s \sum d^{+} (s) = s \sum d^{-} (s) = m$ .

Démonstration

Chaque arête ${u, v}$ est comptée une fois dans $d (u)$ et une fois dans $d (v)$ : la somme des degrés compte donc chaque arête deux fois. Chaque arc $(u, v)$ , lui, est compté une seule fois dans $d^{+} (u)$ et une seule dans $d^{-} (v)$ .

Définition 13.4Chemins et cycles

Un chemin de $u$ à $v$ est une suite de sommets $u = s_{0}, s_{1}, \dots, s_{k} = v$ où chaque $(s_{i}, s_{i + 1})$ est un arc (ou une arête). Sa longueur est $k$ , le nombre d'arcs — et non de sommets.

Un cycle est un chemin de longueur non nulle dont l'origine et l'extrémité coïncident. Dans un graphe non orienté, on exige de plus qu'il n'emprunte pas deux fois la même arête, faute de quoi tout aller-retour serait un cycle.

Définition 13.5Connexité

Un graphe non orienté est connexe si tout couple de sommets est relié par un chemin. Ses composantes connexes sont ses parties connexes maximales.
Un graphe orienté est fortement connexe si pour tout couple $(u, v)$ il existe un chemin de $u$ à $v$ et un de $v$ à $u$ .

AttentionFortement connexe est bien plus fort que connexe

Le graphe orienté $a \to b \to c$ est connexe si l'on oublie les orientations, et n'est pas fortement connexe : on ne revient jamais de $c$ vers $a$ . La différence est celle d'une ville aux rues à sens unique : deux quartiers peuvent sembler voisins sur la carte et n'être joignables que par un long détour, voire pas du tout. La recherche des composantes fortement connexes fait l'objet du chapitre chap:graphes-avances.

Définition 13.6Trois familles remarquables

Un graphe orienté acyclique — un dag — est un graphe orienté sans cycle. Il modélise toute relation de dépendance : tâches à ordonner, cellules d'un tableur, calcul d'un programme. Le lien avec les ordres bien fondés du chapitre chap:induction est exact.
Un arbre est un graphe non orienté connexe et acyclique. Une forêt est un graphe acyclique, c'est-à-dire une réunion disjointe d'arbres.
Un graphe est biparti si l'on peut partager $S$ en deux parties $X$ et $Y$ telles que toute arête relie un sommet de $X$ à un sommet de $Y$ .

iRemarqueDeux définitions de l'arbre, et elles se rejoignent

Le chapitre chap:arbres définissait l'arbre par induction, avec une racine. Ici il est défini comme un graphe connexe acyclique, sans racine privilégiée. Les deux coïncident dès qu'on désigne un sommet comme racine : la structure inductive est alors déterminée. Un arbre au sens des graphes possède exactement $n - 1$ arêtes — une de moins que de sommets — et c'est une caractérisation utile.

Proposition 13.7Caractérisation des graphes bipartis

Un graphe est biparti si et seulement s'il ne contient aucun cycle de longueur impaire.

Démonstration (Sens direct)

Soit $G$ biparti de parties $X$ et $Y$ . Un chemin alterne nécessairement entre $X$ et $Y$ : après un nombre pair d'arêtes on est revenu du même côté, après un nombre impair on est de l'autre. Un cycle revient à son origine, donc du même côté : sa longueur est paire.

iRemarque

La réciproque se démontre par un parcours qui colorie alternativement — c'est exactement l'algorithme de bicolorabilité que le programme cite au chapitre chap:parcours. La caractérisation est donc effective : elle donne un test en $O (n + m)$ .

Définition 13.8Pondération et étiquettes

On peut attacher une valeur aux arcs : une pondération numérique (distance, coût, capacité) ou une étiquette quelconque. Le programme motive cet ajout « par des exemples concrets : graphe de distance, automate fini, diagramme de décision binaire » — et l'automate fini du chapitre chap:automates est exactement cela : un graphe orienté dont les arcs portent des lettres.

13.3 Représenter un graphe

Tout ce qui précède est mathématique. Le choix de la représentation, lui, est informatique — et il décide de la complexité de tous les algorithmes à venir.

13.3.1 Matrice d'adjacence

Définition 13.9Matrice d'adjacence

$M$ est la matrice $n \times n$ définie par $M [u] [v] = 1$ s'il existe un arc de $u$ vers $v$ , et $0$ sinon. Pour un graphe pondéré, on y range le poids, avec une valeur convenue pour l'absence d'arc.


/* Matrice d'adjacence : un tableau statique à deux dimensions. */
#define N_MAX 100
int m[N_MAX][N_MAX];      /* m[u][v] vaut 1 s'il existe un arc u -> v */

13.3.2 Listes d'adjacence

Définition 13.10Listes d'adjacence

À chaque sommet $u$ on associe la liste de ses voisins sortants. La place occupée est alors proportionnelle au nombre d'arcs, et non à son carré.


(* Le graphe ci-dessus, en listes d'adjacence. *)
let g = [| [1; 2]; [3]; []; [2] |]

Méthode : Les listes d'adjacence en C, sans allocation dynamique

Le programme donne une indication précise : « la présentation en C s'effectue à travers des tableaux statiques. Pour la représentation en liste d'adjacence, on peut considérer un tableau à deux dimensions dont les lignes représentent chaque liste avec une sentinelle ou un indicateur de taille en premier indice. »


#define N_MAX 100
#define DEG_MAX 50

/* voisins[u][0] est le NOMBRE de voisins de u ;
   voisins[u][1..voisins[u][0]] sont ces voisins. */
int voisins[N_MAX][DEG_MAX + 1];

/* Ajoute l'arc u -> v. Précondition : voisins[u][0] < DEG_MAX. */
void ajouter_arc(int u, int v) {
    assert(voisins[u][0] < DEG_MAX);
    voisins[u][0] = voisins[u][0] + 1;
    voisins[u][voisins[u][0]] = v;
}

/* Parcourir les voisins de u : */
for (int k = 1; k <= voisins[u][0]; k = k + 1) {
    int v = voisins[u][k];
    /* ... */
}

Aucun malloc, aucun free, aucun pointeur fou : c'est le procédé à retenir pour les épreuves écrites, où l'allocation dynamique est un risque inutile.

13.3.3 Le choix, et il est décisif

ImportantComparer les deux représentations

	Matrice	Listes
Mémoire	$Θ (n^{2})$	$Θ (n + m)$
Tester « l'arc $u \to v$ existe-t-il ? »	$O (1)$	$O (d^{+} (u))$
Parcourir les voisins de $u$	$Θ (n)$	$Θ (d^{+} (u))$
Parcourir tous les arcs	$Θ (n^{2})$	$Θ (n + m)$
Ajouter un arc	$O (1)$	$O (1)$

La ligne décisive est la troisième. Un parcours de graphe visite les voisins de chaque sommet : il coûte $Θ (n^{2})$ avec une matrice et $Θ (n + m)$ avec des listes. Sur le réseau routier français — $1 0^{7}$ sommets, $2 \cdot 1 0^{7}$ arcs — cela fait $1 0^{14}$ contre $3 \cdot 1 0^{7}$ : des jours contre une seconde.

Définition 13.11Graphe creux, graphe dense

Un graphe est creux quand $m = O (n)$ , dense quand $m$ approche $n^{2}$ . La règle :

creux — presque tous les graphes réels — : listes d'adjacence ;
dense, ou si l'on teste sans cesse l'existence d'un arc : matrice.

Le réseau routier a un degré moyen de $4$ : sa matrice occuperait $1 0^{14}$ cases pour $2 \cdot 1 0^{7}$ arcs, soit un remplissage de $2 \cdot 1 0^{- 7}$ . La matrice n'y est pas seulement lente, elle ne tient pas en mémoire.

iRemarqueChaque algorithme aura sa représentation

Le programme le dit pour les deux algorithmes de plus courts chemins : « on présente l'algorithme de Dijkstra … en lien avec la représentation de graphes par listes d'adjacences. On présente l'algorithme de Floyd-Warshall en lien avec la représentation de graphes par matrice d'adjacence. » Ce n'est pas une convention d'exposition : Dijkstra parcourt des voisins, Floyd-Warshall consulte des couples. Chacun est écrit pour la structure qui répond à sa question — chapitre chap:parcours.

Exemple 13.12Une propriété de la matrice qui sert

Si $M$ est la matrice d'adjacence d'un graphe non pondéré, le coefficient $(u, v)$ de $M^{k}$ compte les chemins de longueur exactement $k$ de $u$ à $v$ .

Démonstration (Par récurrence sur

k

)

Vrai pour $k = 1$ par définition. Si c'est vrai pour $k$ , alors

$(M^{k + 1})_{u, v} = w \sum (M^{k})_{u, w} M_{w, v},$

et cette somme compte, pour chaque $w$ , les chemins de longueur $k$ de $u$ à $w$ prolongés par l'arc $w \to v$ lorsqu'il existe. Tout chemin de longueur $k + 1$ est obtenu ainsi, une seule fois, en désignant son avant-dernier sommet.

13.4 Ce qu'il faut retenir

ImportantLe modèle, en cinq points

$G = (S, A)$ , avec $n = ∣ S ∣$ et $m = ∣ A ∣$ ; degrés $d^{+} (s)$ et $d^{-} (s)$ ; $\sum d (s) = 2 m$ .
Connexe (non orienté) et fortement connexe (orienté) sont deux notions très différentes.
Trois familles : dag pour les dépendances, arbre pour les hiérarchies ( $n - 1$ arêtes), biparti pour les appariements — et biparti équivaut à « aucun cycle impair ».
Matrice : $Θ (n^{2})$ de mémoire, test d'arc en $O (1)$ . Listes : $Θ (n + m)$ , parcours des voisins en $Θ (d^{+})$ .
Les graphes réels sont creux. Sauf raison contraire, on prend les listes — et le choix se fait avant d'écrire l'algorithme, pas après.

Continuer sur Adloun : animation, QCM, fiches, exercices