Éducation Nationale Française · ECGappliquées

Graphes

⌚ ~51 min ▢ 6 blocs ✓ 17 exercices ➣ Prérequis : Matrices

Un graphe est l'un des outils de modélisation les plus simples et les plus utiles : un ensemble de sommets (des points) reliés par des arêtes (des liens). Il modélise un réseau routier, les amitiés d'un réseau social, les pages du web, les marchés d'une économie. Ce chapitre fixe le vocabulaire, attache à chaque graphe sa matrice d'adjacence, puis laisse le calcul matriciel du chapitre précédent faire le travail : une seule puissance de matrice $A^d$ compte les chaînes de longueur $d$, et une somme de puissances détecte si le graphe est connexe. On termine par la formule d'Euler reliant les degrés des sommets au nombre d'arêtes.
Conventions utilisées dans tout le chapitre. Tous les graphes sont finis et simples : pas de boucle (pas d'arête d'un sommet vers lui-même) ni d'arête multiple entre deux sommets. L'ensemble des sommets est noté $S$, l'ensemble des arêtes $E$, et la matrice d'adjacence $A$ (le nombre d'arêtes est donc $\mathrm{card}(E) = |E|$, sans conflit avec la matrice $A$). Les matrices, leur produit et leurs puissances $A^d$ sont ceux du chapitre Matrices, rappelés mais non redémontrés ici.

Signaler une erreur

I Graphes et vocabulaire

On commence par les objets eux-mêmes. Un graphe est donné par ses sommets et les arêtes qui les relient ; une arête peut être non orientée (un lien symétrique, comme une amitié) ou orientée (un lien orienté, comme « suit » sur un réseau social). Le nombre de liens en un sommet est son degré, première grandeur numérique attachée à un graphe.

Signaler une erreur

Définition — Graphe

Un graphe est un couple $G = (S, E)$ où $S$ est un ensemble fini de sommets et $E$ un ensemble d'arêtes reliant des sommets.

Dans un graphe non orienté, chaque arête est une paire non ordonnée $\{i, j\}$ de sommets distincts.
Dans un graphe orienté, chaque arête — appelée arc — est un couple ordonné $(i, j)$, dessinée comme une flèche de $i$ vers $j$.

Tous les graphes ici sont simples : pas de boucle (arête d'un sommet vers lui-même) ni d'arête répétée. L'ordre de $G$ est le nombre de sommets $\mathrm{card}(S)$.

Exemple

Le graphe non orienté $G$ utilisé dans tout ce chapitre a pour ensemble de sommets $S = \{1, 2, 3, 4, 5\}$ et pour arêtes $E = \bigl\{ \{1,2\}, \{1,3\}, \{2,3\}, \{3,4\}, \{4,5\} \bigr\}$. Il est d'ordre $5$ et possède $5$ arêtes.

Exemple

Un graphe orienté modélise le web : trois pages $A$, $B$, $C$ avec les liens $A \to B$, $A \to C$, $B \to C$, $C \to A$. Ici l'orientation compte — $A$ pointe vers $B$, mais $B$ ne pointe pas vers $A$.

Définition — Sommets adjacents et degré

Deux sommets reliés par une arête sont adjacents. Dans un graphe non orienté, le degré $d(s)$ d'un sommet $s$ est le nombre d'arêtes incidentes à $s$ (le nombre de sommets adjacents à $s$). Dans un graphe orienté, avec la convention $a_{ij} = 1$ lorsqu'il existe un arc de $i$ vers $j$, le demi-degré extérieur (degré sortant) de $s$ compte les arcs partant de $s$ et le demi-degré intérieur (degré entrant) compte les arcs arrivant en $s$.

Exemple

Sur le graphe $G$ ci-dessus : $d(1) = 2$ (adjacent à $2$ et $3$), $d(2) = 2$, $d(3) = 3$ (adjacent à $1$, $2$, $4$), $d(4) = 2$, $d(5) = 1$. Le sommet $3$ a le plus grand degré — c'est le plus connecté des cinq.

Définition — Graphe complet

Le graphe complet $K_n$ est le graphe simple non orienté à $n$ sommets dans lequel toute paire de sommets distincts est reliée par une arête. Chaque sommet de $K_n$ est de degré $n - 1$.

Exemple

$K_3$ est un triangle ($3$ arêtes) et $K_4$ possède $6$ arêtes ; dans $K_4$ tout sommet est de degré $3$.

Méthode — Modéliser une situation par un graphe

Pour modéliser une situation concrète par un graphe : choisir ce que représentent les sommets (personnes, pages web, marchés, villes), puis ce que représente une arête (une amitié, un lien hypertexte, un flux commercial, une route). Décider si le lien est symétrique — utiliser un graphe non orienté (amitié) — ou orienté — utiliser un graphe orienté (« suit », lien hypertexte). Le degré d'un sommet mesure alors à quel point cette entité est connectée ; les entités les plus centrales (influenceurs, pôles) se lisent comme les sommets de plus haut degré.

Compétences à pratiquer

Lire un graphe et ses degrés

II La matrice d'adjacence

Numéroter les sommets $1, \dots, n$ transforme un graphe en une matrice carrée de $0$ et de $1$ : la matrice d'adjacence. C'est le pont vers le chapitre précédent — une fois le graphe devenu matrice, tout le calcul matriciel (produit, puissances) devient disponible, et c'est ce qu'exploitent les sections suivantes.

Signaler une erreur

Définition — Matrice d'adjacence

Soit $G$ un graphe dont les sommets sont numérotés $1, \dots, n$. Sa matrice d'adjacence est la matrice $A = (a_{ij}) \in \mathcal{M}_n(\mathbb{R})$ définie par $$a_{ij} = \begin{cases} 1 & \text{s'il existe une arête de } i \text{ vers } j, \\ 0 & \text{sinon.} \end{cases}$$ Pour un graphe non orienté, l'arête $\{i,j\}$ pose à la fois $a_{ij} = 1$ et $a_{ji} = 1$.

Exemple

La matrice d'adjacence du graphe non orienté $G$ (sommets $1, \dots, 5$) est $$A = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}.$$ La diagonale est nulle (pas de boucle), et la somme de la $i$-ème ligne est le degré $d(i)$ : la ligne $3$ somme à $3 = d(3)$.

Exemple

La matrice d'adjacence du graphe web orienté ($A = 1$, $B = 2$, $C = 3$ ; liens $A\to B$, $A\to C$, $B\to C$, $C\to A$) est $$\begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}.$$ Elle n'est pas symétrique — l'orientation des arcs est enregistrée par l'asymétrie. Le demi-degré extérieur de $A$ est la somme de la première ligne $2$ ; son demi-degré intérieur est la somme de la première colonne $1$.

Proposition — Symétrie de la matrice d'adjacence non orientée

La matrice d'adjacence d'un graphe non orienté est symétrique : $A = {}^{t}A$.

Preuve

Fixons deux sommets $i$ et $j$. Dans un graphe non orienté l'arête entre eux est la paire non ordonnée $\{i, j\}$ : soit elle est présente, et alors $a_{ij} = a_{ji} = 1$, soit elle est absente, et alors $a_{ij} = a_{ji} = 0$. Dans les deux cas $a_{ij} = a_{ji}$, ce qui est exactement $A = {}^{t}A$.

Exemple

Le programme demande les matrices d'adjacence d'un graphe complet et d'un graphe eulérien. Voici $K_4$ (sommets $1,2,3,4$) et le triangle $K_3$ — ce dernier étant un graphe eulérien, c'est-à-dire admettant une chaîne fermée empruntant chaque arête exactement une fois (notion seulement nommée ici, non développée). Leurs matrices d'adjacence sont $$A_{K_4} = \begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}, \qquad A_{K_3} = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}.$$ Les deux sont symétriques, de diagonale nulle et de somme de ligne constante égale au degré commun.

Méthode — Écrire la matrice d'adjacence et relire le graphe

Graphe $\to$ matrice. Numéroter les sommets une fois pour toutes. Pour chaque $i$, mettre $1$ en colonne $j$ dès qu'il existe une arête de $i$ vers $j$, et $0$ ailleurs. Pour un graphe non orienté le résultat est symétrique ; la diagonale est toujours nulle (graphe simple).
Matrice $\to$ graphe. Réciproquement, une matrice carrée de $0$/$1$ à diagonale nulle est la matrice d'adjacence d'un graphe : dessiner un sommet par indice, et un arc de $i$ vers $j$ pour chaque $a_{ij} = 1$. Si la matrice est symétrique, lire chaque paire symétrique $a_{ij} = a_{ji} = 1$ comme une seule arête non orientée $\{i, j\}$ (un lien, pas deux flèches opposées) : le graphe est non orienté.

Compétences à pratiquer

Écrire la matrice d'adjacence

III Chaînes et puissances de la matrice d'adjacence

Le résultat phare du chapitre : les puissances de la matrice d'adjacence comptent les chaînes. Une chaîne de longueur $d$ est une succession de $d$ arêtes mises bout à bout — les répétitions de sommets et d'arêtes sont autorisées (dans un graphe non orienté on parle de chaîne, dans un graphe orienté de chemin). Le produit matriciel du chapitre Matrices, appliqué à $A$ elle-même, transforme « compter les chaînes de longueur $d$ » en « lire le coefficient de $A^d$ ».

Signaler une erreur

Définition — Chaîne et sa longueur

Une chaîne de longueur $d$ du sommet $i$ au sommet $j$ est une suite de sommets $i = s_0, s_1, \dots, s_d = j$ telle que chaque couple consécutif $(s_{k-1}, s_k)$ soit une arête. Les sommets et les arêtes peuvent se répéter ; une chaîne sans sommet répété est dite simple (chaîne simple / chemin élémentaire). Par convention, la chaîne de longueur $0$ d'un sommet vers lui-même est la chaîne triviale réduite à ce seul sommet. (Dans un graphe non orienté on dit chaîne ; dans un graphe orienté, chemin, chaque pas suivant l'orientation.)

Exemple

Sur le graphe $G$ : $1 - 2 - 3$ est une chaîne de longueur $2$ de $1$ à $3$ (mise en évidence ci-dessous) ; $1 - 3 - 1 - 2$ est une chaîne de longueur $3$ de $1$ à $2$ qui répète le sommet $1$ — les répétitions étant autorisées, c'est une chaîne valide.

Théorème — Dénombrement des chaînes par les puissances

Soit $A$ la matrice d'adjacence d'un graphe à sommets $1, \dots, n$, et soit $d \in \mathbb{N}^{*}$. Alors le coefficient $(A^d)_{ij}$ est exactement le nombre de chaînes de longueur $d$ du sommet $i$ au sommet $j$.

Preuve

Par récurrence sur $d$. Notons $N_d(i, j)$ le nombre de chaînes de longueur $d$ de $i$ à $j$.

Initialisation $d = 1$. Une chaîne de longueur $1$ de $i$ à $j$ est une unique arête de $i$ vers $j$. Il y en a une si $a_{ij} = 1$, aucune si $a_{ij} = 0$. Donc $N_1(i, j) = a_{ij} = (A^1)_{ij}$.
Hérédité. Fixons $d \ge 1$ et supposons $(A^d)_{ij} = N_d(i, j)$ pour tous $i, j$. Une chaîne de longueur $d + 1$ de $i$ à $j$ se décompose de manière unique en une chaîne de longueur $d$ de $i$ vers un sommet intermédiaire $k$, suivie d'une arête de $k$ vers $j$. En sommant sur les $k$ possibles, $$ \begin{aligned} N_{d+1}(i, j) &= \sum_{k=1}^{n} N_d(i, k)\, a_{kj} && \text{(on isole la dernière arête)} \\ &= \sum_{k=1}^{n} (A^d)_{ik}\, a_{kj} && \text{(hypothèse de récurrence)} \\ &= (A^d \cdot A)_{ij} && \text{(définition du produit matriciel)} \\ &= (A^{d+1})_{ij}. && \text{(puissance d'une matrice)} \end{aligned} $$ La propriété est donc vraie au rang $d + 1$.
Conclusion. Par récurrence, $(A^d)_{ij}$ est le nombre de chaînes de longueur $d$ de $i$ à $j$ pour tout $d \in \mathbb{N}^{*}$.

Exemple

Sur le graphe $G$, calculer $A^2$ et lire les chaînes de longueur $2$.

Correction

En élevant au carré la matrice d'adjacence $A$ de $G$, $$A^2 = \begin{pmatrix} 2 & 1 & 1 & 1 & 0 \\ 1 & 2 & 1 & 1 & 0 \\ 1 & 1 & 3 & 0 & 1 \\ 1 & 1 & 0 & 2 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{pmatrix}.$$ D'après le théorème, $(A^2)_{33} = 3$ : il y a trois chaînes de longueur $2$ de $3$ vers $3$, à savoir $3 - 1 - 3$, $3 - 2 - 3$, $3 - 4 - 3$. Et $(A^2)_{13} = 1$ : une seule chaîne de longueur $2$ de $1$ à $3$, à savoir $1 - 2 - 3$.

Méthode — Compter les chaînes de longueur $d$

Pour compter les chaînes de longueur $d$ entre deux sommets : écrire la matrice d'adjacence $A$, calculer la puissance $A^d$ (par les règles du chapitre Matrices), et lire le coefficient. Le coefficient $(i, j)$ de $A^d$ est le nombre de chaînes de longueur exactement $d$ de $i$ à $j$ ; le coefficient diagonal $(A^d)_{ii}$ compte les chaînes fermées de longueur $d$ basées en $i$.

Compétences à pratiquer

Dénombrer les chaînes avec $A^d$

IV Connexité

Un graphe est connexe lorsqu'on peut aller de n'importe quel sommet à n'importe quel autre en suivant ses arêtes. Le théorème de dénombrement transforme cela en un test matriciel : si une puissance $A^d$ (pour $d$ jusqu'à $n - 1$) porte une chaîne entre chaque paire de sommets, le graphe est connexe. Additionner les puissances $I_n + A + \dots + A^{n-1}$ rassemble toutes les longueurs de chaîne jusqu'à $n - 1$ en une seule matrice, dont la positivité est le critère.

Signaler une erreur

Définition — Graphe connexe et fortement connexe

Un graphe non orienté est connexe lorsque, pour toute paire de sommets distincts $i$ et $j$, il existe une chaîne de $i$ à $j$. Un graphe orienté est fortement connexe lorsque, pour tout couple ordonné $(i, j)$, il existe un chemin orienté de $i$ à $j$.

Proposition — Critère de connexité

Soit $G$ un graphe à $n$ sommets de matrice d'adjacence $A$. Alors $G$ est connexe (fortement connexe, s'il est orienté) si et seulement si tout coefficient de la matrice $$B = I_n + A + A^2 + \dots + A^{n-1}$$ est strictement positif.

Preuve

Notons $B_{ij}$ le coefficient $(i,j)$ de $B$. Comme $B = I_n + A + \dots + A^{n-1}$ et que toute puissance $A^d$ est à coefficients positifs ou nuls (elle compte des chaînes), $$B_{ij} = (I_n)_{ij} + \sum_{d=1}^{n-1} (A^d)_{ij},$$ une somme de termes positifs ou nuls ; elle est strictement positive exactement lorsqu'au moins un terme est positif, c'est-à-dire lorsqu'il existe une chaîne d'une certaine longueur $d \in \{0, 1, \dots, n-1\}$ de $i$ à $j$ (la longueur $0$, via $I_n$, couvre le cas $i = j$).

($\Leftarrow$) Supposons tout $B_{ij} > 0$. Alors pour chaque paire $(i, j)$ il existe une chaîne de $i$ à $j$, donc $G$ est connexe.
($\Rightarrow$) Supposons $G$ connexe et fixons $i \neq j$. Il existe une chaîne de $i$ à $j$ ; prenons-en une plus courte. Une plus courte chaîne ne répète jamais de sommet (un sommet répété permettrait de retirer la boucle et de raccourcir la chaîne), donc elle visite au plus $n$ sommets distincts et a donc une longueur au plus $n - 1$. Ainsi $(A^d)_{ij} > 0$ pour un certain $d \le n - 1$, donc $B_{ij} > 0$ ; et $B_{ii} \ge (I_n)_{ii} = 1 > 0$.

Dans les deux sens l'équivalence est établie.

Exemple

Décider si le graphe chaîne $P$ à $3$ sommets ($1 - 2 - 3$) est connexe, à l'aide du critère.

Correction

La matrice d'adjacence et son carré sont $$A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}, \qquad A^2 = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}.$$ Avec $n = 3$, le critère utilise $B = I_3 + A + A^2$ : $$B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} + \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} + \begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix} = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 3 & 1 \\ 1 & 1 & 2 \end{pmatrix}.$$ Tout coefficient de $B$ est strictement positif, donc $P$ est connexe.

Méthode — Tester la connexité

Pour tester si un graphe à $n$ sommets est connexe : former $B = I_n + A + A^2 + \dots + A^{n-1}$ et examiner ses coefficients. Si tout coefficient est strictement positif, le graphe est connexe ; si un coefficient $B_{ij}$ est nul, aucune chaîne de longueur $\le n - 1$ ne relie $i$ à $j$, donc le graphe n'est pas connexe. Une paire inaccessible par une chaîne courte peut le devenir par une plus longue, donc un zéro ne peut être déclaré définitif qu'une fois la somme menée jusqu'à $A^{n-1}$ : ce sont les coefficients de la matrice complète $B$ qui décident.

Compétences à pratiquer

Tester la connexité

V Degré et la formule des poignées de main

Une seule identité relie les degrés de tous les sommets au nombre d'arêtes : chaque arête, ayant deux extrémités, contribue pour $2$ au total des degrés. C'est la formule des poignées de main (que le programme nomme « formule d'Euler »), avec une conséquence de parité immédiate servant à écarter les graphes impossibles.

Signaler une erreur

Proposition — Formule des poignées de main

Dans un graphe non orienté $G = (S, E)$, $$\sum_{s \in S} d(s) = 2\,|E|,$$ la somme des degrés de tous les sommets vaut deux fois le nombre d'arêtes.

Preuve

Comptons de deux façons les couples $(s, e)$ où $s$ est un sommet, $e$ une arête, et $s$ une extrémité de $e$.

En regroupant par sommet $s$ : chaque sommet $s$ appartient à exactement $d(s)$ arêtes, donc le nombre de tels couples est $\sum_{s \in S} d(s)$.
En regroupant par arête $e$ : chaque arête a exactement $2$ extrémités, donc le nombre de tels couples est $2\,|E|$.

Les deux comptages sont égaux, d'où $\sum_{s \in S} d(s) = 2\,|E|$.

Proposition — Le nombre de sommets de degré impair est pair

Dans tout graphe non orienté, le nombre de sommets de degré impair est pair.

Preuve

Séparons la somme des degrés entre les sommets de degré pair et ceux de degré impair : $$\sum_{s \in S} d(s) = \underbrace{\sum_{d(s)\ \text{pair}} d(s)}_{S_{\text{pair}}} + \underbrace{\sum_{d(s)\ \text{impair}} d(s)}_{S_{\text{impair}}}.$$ D'après la formule d'Euler le membre de gauche vaut $2\,|E|$, un nombre pair, et $S_{\text{pair}}$ est pair (somme de nombres pairs). Donc $S_{\text{impair}} = 2\,|E| - S_{\text{pair}}$ est pair. Or $S_{\text{impair}}$ est une somme de nombres impairs ; une somme de nombres impairs n'est paire que lorsqu'il y en a un nombre pair. Donc le nombre de sommets de degré impair est pair.

Exemple

Sur le graphe $G$, les degrés sont $2, 2, 3, 2, 1$, de somme $10 = 2 \times 5 = 2\,|E|$ ($G$ a $5$ arêtes) : la formule d'Euler est vérifiée. Les sommets de degré impair sont $3$ et $5$ — deux d'entre eux, un nombre pair, comme le prédit le corollaire.

Méthode — Écarter un graphe impossible

Pour montrer qu'aucun graphe ne peut réaliser une liste de degrés imposée : sommer les degrés imposés. Si la somme est impaire, aucun graphe n'existe (la formule d'Euler force une somme paire). Plus finement, si la liste a un nombre impair de valeurs impaires, aucun graphe n'existe (le nombre de degrés impairs doit être pair). C'est la première vérification standard sur toute suite de degrés.

Pour aller plus loin

Au-delà du degré, l'analyse des réseaux sociaux attache à un sommet des mesures plus fines — sa centralité, son intermédiarité — pour détecter influenceurs ou goulots d'étranglement ; elles ne sont pas exigibles à ce niveau, mais reposent exactement sur le calcul matriciel d'adjacence de ce chapitre. La question compagne « quelle est la route la plus courte entre deux sommets d'un graphe pondéré ? » est algorithmique : elle est étudiée, avec l'algorithme de Dijkstra, dans le chapitre Algorithmique et Python, où les graphes réapparaissent implémentés par listes et matrices d'adjacence.

Signaler une erreur

Compétences à pratiquer

Appliquer la formule des poignées de main

VI Pour aller plus loin

Compétences à pratiquer

Modéliser et analyser une situation