Le modèle des graphes

Cours · informatique (MP2I/MPI), chapitre 13 · MP2I et MPI · le début du chapitre, la suite sur Adloun

Un graphe : des sommets reliés par des arêtes.

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.

Exercices du chapitre

Sept sommets de degré trois corrigé
Un arbre a exactement $n - 1$ arêtes corrigé
Tout graphe orienté acyclique possède une source corrigé
Les puissances de la matrice comptent les chemins corrigé
Problème — Un graphe pour un problème qui n'en a pas l'air corrigé
Problème — Du tableau rectangulaire au tableau de départs corrigé

La suite du cours · Tous les exercices du chapitre