Comment compter le nombre de chemins de longueur $n$ entre deux sommets d'un graphe ?

On écrit la matrice d'adjacence $A$ du graphe (en fixant un ordre des sommets), puis on calcule $A^n$ à la calculatrice ou à la main. Le coefficient situé ligne $i$, colonne $j$ de $A^n$ est exactement le nombre de chemins de longueur $n$ allant du sommet $i$ au sommet $j$. Le résultat vaut pour les graphes non orientés comme pour les graphes orientés.

Quelle différence entre une chaîne, un cycle et un chemin de longueur $n$ ?

Une chaîne est une suite de sommets consécutivement adjacents ; sa longueur est son nombre d'arêtes. Un cycle est une chaîne fermée (même sommet au départ et à l'arrivée) sans répéter d'arête. Dans le comptage par $A^n$, un « chemin de longueur $n$ » est n'importe quelle chaîne de $n$ arêtes, avec répétitions de sommets ou d'arêtes autorisées : c'est pour cela que $(A^2)_{ii}$ vaut le degré de $i$ (aller-retour sur chaque arête).

À quoi reconnaît-on qu'un graphe est connexe ou qu'il admet une chaîne eulérienne ?

Un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne : on le vérifie en parcourant le graphe à partir d'un sommet. Un graphe connexe admet une chaîne eulérienne (passant une fois et une seule par chaque arête) si et seulement s'il a 0 ou 2 sommets de degré impair ; s'il en a 0, la chaîne est fermée (cycle eulérien) et on peut partir de n'importe quel sommet.

Graphes — BgMaths

Définitions

Définition 1 — graphe, sommets, arêtes, degré. Un graphe est formé d’un ensemble fini de sommets et d’un ensemble d’arêtes, chaque arête reliant deux sommets (éventuellement le même : boucle). Deux sommets reliés par une arête sont adjacents. L’ordre du graphe est son nombre de sommets ; le degré $d(s)$ d’un sommet $s$ est le nombre d’arêtes dont il est une extrémité (une boucle compte pour $2$ ).

Définition 2 — graphe simple, graphe complet. Un graphe est simple s’il n’a ni boucle ni arête multiple. Le graphe complet $K_n$ est le graphe simple à $n$ sommets dans lequel deux sommets distincts quelconques sont toujours adjacents.

Définition 3 — chaîne, cycle, connexité. 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 son premier et son dernier sommet sont identiques ; un cycle est une chaîne fermée qui n’emprunte 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 ; sinon, il se décompose en composantes connexes.

Définition 4 — graphe orienté, chemin. Dans un graphe orienté, chaque arête, appelée arc, possède un sens : l’arc $A \to B$ va de $A$ vers $B$ . Un chemin est une suite d’arcs consécutifs ; sa longueur est son nombre d’arcs. Les graphes orientés modélisent les relations non symétriques : sens uniques, liens entre pages web (PageRank), évolution d’un système (chaînes de Markov).

Définition 5 — matrice d’adjacence. On numérote les sommets de $1$ à $n$ . La matrice d’adjacence du graphe est la matrice carrée $A = (a_{ij})$ d’ordre $n$ dont le coefficient $a_{ij}$ est le nombre d’arêtes (ou d’arcs) allant du sommet $i$ au sommet $j$ . Pour un graphe non orienté, $A$ est symétrique et la somme de la ligne $i$ vaut $d(i)$ (graphe simple) ; pour un graphe orienté, la ligne $i$ décrit les arcs qui partent de $i$ et la colonne $j$ ceux qui arrivent en $j$ . Pour un graphe simple, la diagonale est nulle.

Définition 6 — chaîne et cycle eulériens. Une chaîne eulérienne est une chaîne qui emprunte chaque arête une fois et une seule ; si elle est fermée, on parle de cycle eulérien. (Problème historique des ponts de Königsberg, résolu par Euler en 1736.)

Théorèmes et propriétés

Théorème 1 (lemme des poignées de mains). (démonstration exigible) Dans tout graphe, la somme des degrés des sommets est égale au double du nombre d’arêtes :

$\sum_{s} d(s) = 2 \times (\text{nombre d'arêtes})$

Démonstration : chaque arête possède deux extrémités et contribue donc pour $2$ à la somme des degrés. $\square$

Conséquence : la somme des degrés est paire, donc le nombre de sommets de degré impair est pair. Il n’existe pas, par exemple, de graphe dont les degrés seraient $3, 3, 2, 2, 1$ (somme $11$ ).

Théorème 2 (arêtes du graphe complet). Dans $K_n$ , chaque sommet est de degré $n - 1$ et le nombre d’arêtes vaut

$\frac{n(n-1)}{2}$

C’est le nombre de paires de sommets distincts ; on le retrouve par le Théorème 1 : $\frac{n(n-1)}{2} = \frac{1}{2}\sum d(s)$ . Exemple : $K_6$ a $\dfrac{6 \times 5}{2} = 15$ arêtes.

Théorème 3 (nombre de chemins de longueur $n$ ). (démonstration exigible, par récurrence) Soit $A$ la matrice d’adjacence d’un graphe (orienté ou non) et $n \geq 1$ un entier. Le coefficient $(A^n)_{ij}$ est le nombre de chemins de longueur $n$ allant du sommet $i$ au sommet $j$ (suites de $n$ arêtes consécutives, répétitions de sommets ou d’arêtes autorisées).

Démonstration : initialisation, $(A^1)_{ij} = a_{ij}$ est le nombre d’arêtes de $i$ à $j$ . Hérédité : un chemin de longueur $n+1$ de $i$ à $j$ est un chemin de longueur $n$ de $i$ vers un sommet $k$ , suivi d’une arête de $k$ à $j$ ; pour $k$ fixé il y en a $(A^n)_{ik}\,a_{kj}$ , et en sommant sur les $p$ sommets intermédiaires possibles : $\sum_{k=1}^{p} (A^n)_{ik}\, a_{kj} = (A^nA)_{ij} = (A^{n+1})_{ij}$ . $\square$

Conséquences : dans un graphe simple non orienté, $(A^2)_{ii} = d(i)$ (un aller-retour par arête incidente) ; le plus court chemin de $i$ à $j$ a pour longueur le plus petit entier $n$ tel que $(A^n)_{ij} \neq 0$ .

Théorème 4 (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 s’il a exactement deux sommets de degré impair ; ces deux sommets en sont alors les extrémités.

Idée de la condition nécessaire : chaque passage par un sommet intermédiaire utilise deux arêtes (une pour arriver, une pour repartir), donc son degré est pair ; seuls le sommet de départ et celui d’arrivée peuvent être de degré impair.

Méthodes

Méthode 1 — exploiter le lemme des poignées de mains.

Calculer la somme des degrés (ou la lire dans l’énoncé).
Diviser par $2$ pour obtenir le nombre d’arêtes (Théorème 1).
Pour tester l’existence d’un graphe : vérifier que la somme des degrés est paire, c’est-à-dire que le nombre de sommets de degré impair est pair.

Exemple : des degrés $2, 3, 3, 4$ donnent $\frac{12}{2} = 6$ arêtes ; des degrés $3, 3, 2, 2, 1$ (somme $11$ ) sont impossibles.

Méthode 2 — écrire la matrice d’adjacence.

Fixer l’ordre des sommets (celui de l’énoncé).
Lister les arêtes (ou les arcs) : $a_{ij} = 1$ si $i$ et $j$ sont reliés (ligne = départ, colonne = arrivée pour un graphe orienté), $0$ sinon.
Contrôler : matrice symétrique et diagonale nulle pour un graphe simple non orienté ; somme de la ligne $i$ égale à $d(i)$ .

Exemple : le graphe d’arêtes $AB$ , $AC$ , $BC$ , $CD$ a pour matrice $A = \begin{pmatrix} 0&1&1&0 \\ 1&0&1&0 \\ 1&1&0&1 \\ 0&0&1&0 \end{pmatrix}$ ; le graphe orienté d’arcs $A \to B$ , $B \to C$ , $C \to A$ , $A \to C$ a pour matrice $M = \begin{pmatrix} 0&1&1 \\ 0&0&1 \\ 1&0&0 \end{pmatrix}$ , non symétrique.

Méthode 3 — compter les chemins de longueur $n$ .

Écrire la matrice d’adjacence $A$ (Méthode 2).
Calculer $A^n$ (à la main pour $n = 2$ ou $3$ , sinon à la calculatrice ou en Python).
Lire le coefficient ligne $i$ , colonne $j$ : c’est le nombre de chemins de longueur $n$ de $i$ à $j$ (Théorème 3), à vérifier si possible en listant les chemins.

def produit(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
    return C

def puissance(A, n):
    n_som = len(A)
    P = [[1 if i == j else 0 for j in range(n_som)] for i in range(n_som)]  # identité
    for _ in range(n):
        P = produit(P, A)
    return P

A = [[0, 1, 1, 0],
     [1, 0, 1, 0],
     [1, 1, 0, 1],
     [0, 0, 1, 0]]
print(puissance(A, 3)[0][0])   # 2 : chemins de longueur 3 de A à A

Exemple : avec le graphe $AB$ , $AC$ , $BC$ , $CD$ : $A^2 = \begin{pmatrix} 2&1&1&1 \\ 1&2&1&1 \\ 1&1&3&0 \\ 1&1&0&1 \end{pmatrix}$ , donc $(A^2)_{AD} = 1$ (l’unique chemin $A - C - D$ ) et $(A^2)_{CC} = 3 = d(C)$ .

Méthode 4 — décider de l’existence d’une chaîne eulérienne.

Vérifier que le graphe est connexe (Définition 3).
Compter les sommets de degré impair.
Conclure avec le Théorème 4 : $0$ sommet impair = cycle eulérien (départ quelconque) ; $2$ sommets impairs = chaîne eulérienne entre ces deux sommets ; sinon, aucun parcours eulérien.

Exemple : le graphe d’arêtes $AB$ , $AC$ , $BC$ , $CD$ a deux sommets de degré impair ( $C$ de degré $3$ , $D$ de degré $1$ ) : $D - C - A - B - C$ est une chaîne eulérienne de $D$ à $C$ . Les ponts de Königsberg (quatre sommets impairs) n’admettent aucun parcours.

Définitions

Théorèmes et propriétés

Méthodes

Reste informé