Graphes et matrices d'adjacence

Ce que tu sais déjà. Tu sais multiplier des matrices et calculer leurs puissances (Matrices : calcul matriciel et applications). Un graphe représente des objets (les sommets) et des liens entre eux (les arêtes) : réseaux routiers, réseaux sociaux, liaisons aériennes, circuits électriques, pages web. Les matrices permettent de faire des calculs sur ces réseaux.

1. Graphes, degrés

Définitions.

• Un graphe (non orienté) est formé de sommets et d’arêtes reliant certains couples de 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 tous ses sommets sont adjacents deux à deux. Le graphe complet d’ordre $n$ se note $K_n$.

Propriété (lemme des poignées de main). La somme des degrés des sommets d’un graphe est égale au double du nombre d’arêtes.

Justification. Chaque arête a deux extrémités : elle est comptée exactement deux fois dans la somme des degrés.

Conséquences. Le nombre de sommets de degré impair est toujours pair. Le graphe complet $K_n$ a $\dfrac{n(n - 1)}{2}$ arêtes (chacun des $n$ sommets est de degré $n - 1$).

Exemple. Dans un tournoi où $6$ équipes se rencontrent toutes une fois, il y a $\dfrac{6 \times 5}{2} = 15$ matchs (arêtes de $K_6$). Peut-on avoir $7$ personnes qui ont chacune serré la main à exactement $3$ autres ? Non : la somme des degrés vaudrait $21$, nombre impair.

→ S’entraîner : Exercice 1 · Exercice 2

2. Chaînes et connexité

Définitions.

• 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 point de départ ; un cycle est une chaîne fermée qui n’utilise pas deux fois la même arête.
• Un graphe est connexe si deux sommets quelconques peuvent toujours être reliés par une chaîne.

Exemple (figure 1). $A - B - C - E$ est une chaîne de longueur $3$ ; $A - B - D - A$ est un cycle de longueur $3$. Le graphe est connexe.

Graphes orientés. Quand les liens ont un sens (sens unique, « suivre » quelqu’un sur un réseau), on utilise des arcs (flèches). On parle alors de chemins au lieu de chaînes.

→ S’entraîner : Exercice 3

3. Matrice d’adjacence

Définition. On numérote les sommets $1$, $2$, …, $n$. La matrice d’adjacence du graphe est la matrice carrée $A$ d’ordre $n$ dont le coefficient $a_{ij}$ est le nombre d’arêtes (ou d’arcs, pour un graphe orienté) allant du sommet $i$ au sommet $j$.

• Pour un graphe non orienté, $A$ est symétrique ($a_{ij} = a_{ji}$) ; la somme des coefficients de la ligne $i$ est le degré du sommet $i$.
• Pour un graphe orienté, $a_{ij} = 1$ s’il y a un arc de $i$ vers $j$, $0$ sinon.

→ S’entraîner : Exercice 4

4. Compter les chemins avec les puissances de A

Théorème. Soit $A$ la matrice d’adjacence d’un graphe (orienté ou non) et $n \geqslant 1$. Le coefficient $(i, j)$ de $A^n$ est le nombre de chemins (ou chaînes) de longueur $n$ allant du sommet $i$ au sommet $j$.

Exemple (figure 2). Avec la matrice $A$ du graphe orienté : $A^2 = \begin{pmatrix} 1 & 0 & 1 & 2 \\ 2 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 \end{pmatrix}$ et $A^3 = \begin{pmatrix} 3 & 1 & 1 & 1 \\ 1 & 2 & 2 & 0 \\ 1 & 1 & 2 & 2 \\ 1 & 0 & 1 & 2 \end{pmatrix}$.

• Le coefficient $(1, 4)$ de $A^2$ vaut $2$ : il y a deux chemins de longueur $2$ de $1$ à $4$, à savoir $1 \to 2 \to 4$ et $1 \to 3 \to 4$.
• Le coefficient $(1, 4)$ de $A^3$ vaut $1$ : un seul chemin de longueur $3$, $1 \to 2 \to 3 \to 4$.
• Le coefficient $(1, 1)$ de $A^3$ vaut $3$ : trois chemins de longueur $3$ partent de $1$ et y reviennent ($1 \to 2 \to 4 \to 1$, $1 \to 3 \to 4 \to 1$ et $1 \to 2 \to 3 \to 1$).

Pour de grands graphes, on laisse la machine calculer :

import numpy as np
A = np.array([[0, 1, 1, 0],
              [0, 0, 1, 1],
              [1, 0, 0, 1],
              [1, 0, 0, 0]])
A3 = np.linalg.matrix_power(A, 3)
print(A3[0, 3])   # chemins de longueur 3 de 1 à 4 : 1

→ S’entraîner : Exercice 5 · Exercice 6

5. Graphes eulériens (pour aller plus loin)

Définition. Une chaîne eulérienne passe une fois et une seule par chaque arête du graphe. Si elle est fermée, c’est un cycle eulérien.

Théorème d’Euler (admis). 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 sommets sont de degré impair (la chaîne part de l’un et arrive à l’autre).

Exemple historique. En 1736, Euler montre qu’il est impossible de traverser les sept ponts de Königsberg une seule fois chacun : le graphe correspondant a quatre sommets de degré impair.

→ S’entraîner : Exercice 7

À retenir.

• Somme des degrés $= 2 \times$ nombre d’arêtes ; $K_n$ a $\dfrac{n(n - 1)}{2}$ arêtes.
• Chaîne, longueur, graphe connexe ; chemins dans un graphe orienté.
• Matrice d’adjacence : $a_{ij}$ = nombre d’arêtes (arcs) de $i$ vers $j$ ; symétrique si le graphe n’est pas orienté.
• Le coefficient $(i, j)$ de $A^n$ compte les chemins de longueur $n$ de $i$ à $j$.
• Euler : cycle eulérien $\iff$ tous les degrés pairs (graphe connexe) ; chaîne eulérienne $\iff$ $0$ ou $2$ sommets de degré impair.