Graphes

Des points reliés par des traits : réseaux routiers, réseaux sociaux, circuits électriques, molécules… Les graphes modélisent toutes les situations où des objets sont en relation. Avec leur matrice d'adjacence, compter les chemins devient un simple calcul de puissances.

  • Modéliser une situation par un graphe, utiliser le vocabulaire
  • Utiliser la relation entre degrés et nombre d'arêtes
  • Écrire la matrice d'adjacence d'un graphe
  • Calculer le nombre de chemins de longueur donnée entre deux sommets

Cours

1. Vocabulaire

Un graphe est formé de sommets et d'arêtes ; chaque arête relie deux sommets. L'ordre du graphe est son nombre de sommets.

  • Deux sommets reliés par une arête sont adjacents.
  • Le degré d'un sommet est le nombre d'arêtes dont il est une extrémité.
  • Un graphe est complet si deux sommets distincts quelconques sont toujours adjacents. Le graphe complet d'ordre $n$ est noté $K_n$.

Une chaîne est une suite de sommets dans laquelle deux sommets consécutifs sont adjacents ; sa longueur est le nombre d'arêtes parcourues. Une chaîne est fermée si elle revient à son sommet de départ ; un cycle est une chaîne fermée dont les arêtes sont toutes distinctes.

Un graphe est connexe si deux sommets quelconques peuvent toujours être reliés par une chaîne (il est « d'un seul tenant »).

Dans un graphe orienté, les arêtes sont des arcs (flèches), qui vont d'un sommet vers un autre. On parle alors de chemins, qui respectent le sens des flèches. Exemple : les liens entre pages web.

Dans un graphe non orienté, la somme des degrés des sommets est égale au double du nombre d'arêtes. Par conséquent, le nombre de sommets de degré impair est pair.

Preuve du lemme.

Chaque arête a deux extrémités : quand on additionne les degrés, elle est comptée exactement deux fois (une fois pour chaque extrémité). La somme des degrés vaut donc $2 \times$ (nombre d'arêtes), qui est pair. Une somme d'entiers est paire seulement si elle contient un nombre pair de termes impairs. $\blacksquare$

Dans $K_n$, chaque sommet a pour degré $n - 1$ : la somme des degrés est $n(n - 1)$, donc $K_n$ a $\dfrac{n(n-1)}{2} = \dbinom n2$ arêtes. Un tournoi de 8 équipes où chacune rencontre toutes les autres compte 28 matchs.

2. Matrice d'adjacence

Les sommets étant numérotés de 1 à $n$, la matrice d'adjacence du graphe est la matrice carrée $M$ d'ordre $n$ dont le coefficient $m_{ij}$ est le nombre d'arêtes (ou d'arcs) reliant le sommet $i$ au sommet $j$.

Pour un graphe non orienté, $M$ est symétrique ($m_{ij} = m_{ji}$) et la somme des coefficients de la ligne $i$ est le degré du sommet $i$.

Triangle $K_3$ : $M = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0\end{pmatrix}$ et $M^2 = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 1 \\ 1 & 1 & 2\end{pmatrix}$. Il y a 2 chemins de longueur 2 de 1 à 1 (1–2–1 et 1–3–1), et un seul de 1 à 2 (1–3–2).

3. Nombre de chemins

Soit $M$ la matrice d'adjacence d'un graphe (orienté ou non) et $n \geqslant 1$. Le coefficient $(i, j)$ de $M^n$ est égal au nombre de chemins (ou de chaînes) de longueur $n$ allant du sommet $i$ au sommet $j$.

Par récurrence sur $n$. Notons $c_{ij}^{(n)}$ le nombre de chemins de longueur $n$ de $i$ à $j$.

Initialisation. Un chemin de longueur 1 de $i$ à $j$ est une arête (un arc) de $i$ vers $j$ : $c_{ij}^{(1)} = m_{ij}$, coefficient de $M^1$.

Hérédité. Supposons que $c_{ik}^{(n)}$ soit le coefficient $(i, k)$ de $M^n$ pour tous $i$, $k$. Un chemin de longueur $n + 1$ de $i$ à $j$ se décompose de façon unique en un chemin de longueur $n$ de $i$ à un sommet $k$ (l'avant-dernier sommet), suivi d'une arête de $k$ à $j$.

  • Pour un $k$ fixé, il y a $c_{ik}^{(n)} \times m_{kj}$ tels chemins (principe multiplicatif).
  • En sommant sur les valeurs possibles de $k$ (cas disjoints, principe additif) : $$c_{ij}^{(n+1)} = \sum_{k=1}^{p}c_{ik}^{(n)}m_{kj} = \sum_{k=1}^{p}\left(M^n\right)_{ik}m_{kj} = \left(M^nM\right)_{ij} = \left(M^{n+1}\right)_{ij}.$$

La propriété est vraie pour tout $n \geqslant 1$. $\blacksquare$

La distance entre deux sommets est la longueur d'une plus courte chaîne qui les relie : c'est le plus petit $n$ tel que le coefficient $(i, j)$ de $M^n$ soit non nul. Un graphe d'ordre $p$ est connexe si et seulement si, pour tous $i \neq j$, l'un des coefficients $(i, j)$ de $M, M^2, \dots, M^{p-1}$ est non nul.

4. Graphes eulériens

Une chaîne eulérienne est une chaîne qui passe une et une seule fois par chaque arête du graphe. C'est le problème du dessin « sans lever le crayon ». Si elle est fermée, c'est un cycle eulérien.

Un graphe connexe admet :

  • un cycle eulérien si et seulement si tous ses sommets sont de degré pair ;
  • une chaîne eulérienne non fermée si et seulement si exactement deux de ses sommets sont de degré impair (la chaîne va alors de l'un à l'autre).

Le sens « nécessaire » est facile : à chaque passage par un sommet intermédiaire, la chaîne utilise deux arêtes (une pour entrer, une pour sortir). Seuls le départ et l'arrivée peuvent donc avoir un degré impair.

La ville de Königsberg (aujourd'hui Kaliningrad) avait sept ponts reliant deux îles et les rives. Peut-on se promener en traversant chaque pont une seule fois ? En 1736, Euler prouve que c'est impossible : les quatre zones sont de degré impair. Son raisonnement est considéré comme l'acte de naissance de la théorie des graphes.

Méthodes à connaître

  1. Écris la matrice d'adjacence $M$ (coefficient $i, j$ : nombre d'arêtes de $i$ vers $j$).
  2. Calcule $M^n$ (calculatrice).
  3. Le coefficient ligne $i$, colonne $j$ de $M^n$ est le nombre de chemins de longueur $n$ de $i$ à $j$.
  1. Vérifie que le graphe est connexe.
  2. Compte les sommets de degré impair.
  3. 0 sommet impair : cycle eulérien ; 2 sommets impairs : chaîne eulérienne entre ces deux sommets ; plus de 2 : impossible (théorème d'Euler).

Mini-jeux

Exercices

Existe-t-il un graphe dont les sommets ont pour degrés 3, 3, 3 ? Et 3, 3, 3, 3 ? Et 1, 2, 2, 3, 4 ?

3, 3, 3 : somme 9 impaire, impossible. 3, 3, 3, 3 : oui, $K_4$. 1, 2, 2, 3, 4 : somme 12, paire ; par exemple les sommets $A$ (4) relié à $B, C, D, E$, puis $B$ (3) relié à $C$ et $D$ : degrés $A:4$, $B:3$, $C:2$, $D:2$, $E:1$. Oui.

Dans un tournoi, 12 équipes se rencontrent chacune une fois. Combien de matchs sont joués ?

C'est le nombre d'arêtes de $K_{12}$ : $\frac{12 \times 11}{2} = 66$.

Un graphe a pour matrice d'adjacence $M = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0\end{pmatrix}$. Dessiner le graphe, donner les degrés et le nombre d'arêtes. Est-il connexe ?

Arêtes : 1–2, 1–4, 2–3, 2–4. Degrés : 2, 3, 1, 2 (somme 8 = 2 × 4 arêtes). Connexe : tous les sommets sont reliés à 2.

Avec la matrice de $K_3$ du cours, calculer $M^3$. Combien y a-t-il de chaînes fermées de longueur 3 partant du sommet 1 ? Les décrire.

Nombre :

$M^3 = M^2M = \begin{pmatrix} 2 & 3 & 3 \\ 3 & 2 & 3 \\ 3 & 3 & 2\end{pmatrix}$. Le coefficient $(1, 1)$ vaut 2 : 1–2–3–1 et 1–3–2–1 (le tour du triangle dans les deux sens).

Un musée a 5 salles $A$, $B$, $C$, $D$, $E$. Les portes relient $A$–$B$, $A$–$C$, $B$–$C$, $B$–$D$, $C$–$D$, $C$–$E$, $D$–$E$ et $D$–$E$ (deux portes). Peut-on visiter le musée en franchissant chaque porte une et une seule fois ? Si oui, d'où partir ?

Degrés : $A:2$, $B:3$, $C:4$, $D:4$, $E:3$. Le graphe est connexe et a exactement deux sommets de degré impair, $B$ et $E$ : il existe une chaîne eulérienne de $B$ à $E$. Par exemple $B$–$A$–$C$–$B$–$D$–$C$–$E$–$D$–$E$.

Dans le graphe « carré $1$–$2$–$3$–$4$–$1$ » (sans diagonale), calculer $M^2$ et en déduire la distance entre les sommets 1 et 3.

$M = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}$, $M^2 = \begin{pmatrix} 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \\ 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2\end{pmatrix}$. $m_{13} = 0$ mais $(M^2)_{13} = 2 \neq 0$ : la distance vaut 2.

Dans un groupe de $n \geqslant 2$ personnes, montrer que deux personnes au moins ont le même nombre d'amis dans le groupe (l'amitié étant réciproque).

On modélise par un graphe à $n$ sommets ; les degrés possibles sont $0, 1, \dots, n - 1$. Mais 0 et $n - 1$ ne peuvent pas être atteints tous les deux (quelqu'un d'ami avec tout le monde empêche quelqu'un de n'avoir aucun ami). Il reste $n - 1$ valeurs pour $n$ sommets : deux sommets ont le même degré (principe des tiroirs).

Quatre pages web : 1 pointe vers 2 et 3 ; 2 pointe vers 3 ; 3 pointe vers 1 et 4 ; 4 pointe vers 1. Écrire la matrice d'adjacence $M$ (graphe orienté), puis calculer le nombre de chemins de longueur 3 allant de 1 à 4.

$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}$. $M^2 = \begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0\end{pmatrix}$, et $(M^3)_{14} = $ ligne 1 de $M^2$ fois colonne 4 de $M$ $= 1 \times 0 + 0 \times 0 + 1 \times 1 + 1 \times 0 = 1$ : un seul chemin, 1 → 2 → 3 → 4.