Théorie des graphes

Cours complet · mathématiques appliquées (ECG 1re année), chapitre 3 · prépa ECG, 1re année

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

Un graphe fini est un outil de modélisation simple et redoutablement efficace : il représente des objets et les liens entre eux. Les sciences sociales s'en servent pour les réseaux d'individus, l'économie pour des modèles d'évolution, l'informatique pour le réseau des pages web — celui-ci compte plusieurs dizaines de milliards de sommets, et c'est un calcul de graphe qui décide de l'ordre des résultats d'une recherche.

L'intérêt de ce chapitre, placé juste après le calcul matriciel, tient en une phrase : un graphe se range dans une matrice, et les puissances de cette matrice répondent à des questions qu'on ne saurait pas traiter autrement.

3.1 Vocabulaire

Définition 3.1Graphe

Un graphe $G$ est la donnée d'un ensemble fini $S$ de sommets et d'un ensemble d'arêtes reliant certains couples de sommets. Deux sommets reliés par une arête sont dits adjacents. Le graphe est orienté lorsque ses arêtes ont un sens (on parle alors d'arcs), non orienté sinon.

Exemple 3.2Deux lectures d'une même situation

Un réseau d'amitiés est naturellement non orienté : si $A$ est ami avec $B$ , $B$ l'est avec $A$ . Un réseau d'abonnements ne l'est pas : $A$ peut suivre $B$ sans réciproque. Le choix d'orienter ou non n'est pas technique, il traduit la nature du lien modélisé.

Définition 3.3Degré d'un sommet

Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes qui en partent.

◆Théorème 3.4Formule d'Euler, dite des poignées de main

Dans un graphe non orienté à $m$ arêtes, la somme des degrés de tous les sommets vaut $2 m$ :

$s \in S \sum de g (s) = 2 m .$

Démonstration

Comptons les couples (sommet, arête issue de ce sommet). En regroupant par sommet, ce nombre vaut $\sum_{s} de g (s)$ . En regroupant par arête, chaque arête a exactement deux extrémités et fournit donc deux couples : le total vaut $2 m$ . Les deux comptages portent sur le même ensemble.

iRemarqueLe nom

Dans une assemblée, chaque poignée de main engage deux personnes : le nombre total de mains serrées est donc le double du nombre de poignées. Il en découle qu'un graphe a toujours un nombre pair de sommets de degré impair, car une somme d'entiers valant $2 m$ ne peut contenir un nombre impair de termes impairs.

3.2 Matrice d'adjacence

Définition 3.5Matrice d'adjacence

Soit $G$ un graphe dont les sommets sont numérotés de $1$ à $n$ . Sa matrice d'adjacence est la matrice $A \in M_{n} (R)$ définie par

$a_{ij} = {10 s’il existe une ar e ˆ te de i vers j, sinon.$

Proposition 3.6Graphe non orienté et symétrie

Un graphe est non orienté si et seulement si sa matrice d'adjacence est symétrique.

Démonstration

Une arête entre $i$ et $j$ sans orientation se lit dans les deux sens : elle impose $a_{ij} = a_{j i} = 1$ . Réciproquement, si $A =^{t} A$ , tout lien de $i$ vers $j$ s'accompagne du lien de $j$ vers $i$ .

iRemarqueLa numérotation est un choix

Renuméroter les sommets change la matrice, pas le graphe. Deux matrices différentes peuvent donc décrire le même objet — c'est le prix à payer pour disposer d'un tableau de nombres.

Exemple 3.7Le graphe complet

Le graphe complet à $n$ sommets, noté $K_{n}$ , relie chaque paire de sommets. Sa matrice d'adjacence a des $0$ sur la diagonale et des $1$ partout ailleurs ; chaque sommet est de degré $n - 1$ , et le nombre d'arêtes vaut $\frac{n ( n - 1 )}{2} = (2 n)$ d'après la formule d'Euler.

3.3 Chemins et puissances de la matrice

Définition 3.8Chaîne, chemin, longueur

Une chaîne (ou, dans un graphe orienté, un chemin) de $i$ à $j$ est une suite de sommets $i = s_{0}, s_{1}, \dots, s_{d} = j$ dans laquelle deux sommets consécutifs sont reliés par une arête. Sa longueur est $d$ , c'est-à-dire le nombre d'arêtes empruntées.

◆Théorème 3.9Le théorème des puissances

Soit $A$ la matrice d'adjacence d'un graphe à $n$ sommets. Pour tout $d \in N^{*}$ , le coefficient de position $(i, j)$ de $A^{d}$ est le nombre de chemins de longueur $d$ allant du sommet $i$ au sommet $j$ .

Démonstration

Par récurrence sur $d$ . Pour $d = 1$ , $a_{ij}$ vaut $1$ s'il y a une arête de $i$ vers $j$ , et $0$ sinon : c'est bien le nombre de chemins de longueur $1$ .

Supposons la propriété vraie au rang $d$ . Un chemin de longueur $d + 1$ de $i$ à $j$ se décompose de façon unique en un chemin de longueur $d$ de $i$ vers un sommet intermédiaire $k$ , suivi d'une arête de $k$ vers $j$ . En sommant sur toutes les valeurs possibles de $k$ , le nombre de tels chemins vaut

$k = 1 \sum n (A^{d})_{ik} \times a_{k j} = (A^{d} A)_{ij} = (A^{d + 1})_{ij},$

puisque $(A^{d})_{ik}$ compte les chemins de longueur $d$ de $i$ à $k$ par hypothèse de récurrence, et $a_{k j}$ vaut $1$ ou $0$ selon que la dernière arête existe ou non.

ImportantPourquoi c'est le produit matriciel

La démonstration ne fait qu'écrire la définition du produit : $\sum_{k} (A^{d})_{ik} a_{k j}$ . Le produit matriciel est exactement le comptage des façons d'aller de $i$ à $j$ en passant par un intermédiaire. C'est là que le chapitre précédent et celui-ci se rejoignent.

Exemple 3.10Compter les chemins

Sur le graphe ci-dessus, $A^{2}$ a pour coefficient $(1, 3)$ le nombre de chaînes de longueur $2$ de $1$ à $3$ . Il n'y en a qu'une : $1 - 2 - 3$ . Le coefficient $(1, 1)$ de $A^{2}$ vaut $de g (1) = 2$ — les chaînes de longueur $2$ d'un sommet vers lui-même sont les allers-retours sur chacune de ses arêtes.

iRemarqueLa diagonale de

A^{2}

De façon générale, pour un graphe non orienté, $(A^{2})_{ii} = de g (i)$ . La trace de $A^{2}$ vaut donc $\sum_{i} de g (i) = 2 m$ : la formule d'Euler se relit sur les matrices.

3.4 Connexité

Définition 3.11Graphe connexe

Un graphe est connexe lorsque, pour tout couple de sommets $(i, j)$ , il existe une chaîne allant de $i$ à $j$ . Autrement dit : le graphe est d'un seul tenant.

◆Théorème 3.12Critère matriciel de connexité

Soit $G$ un graphe à $n$ sommets, de matrice d'adjacence $A$ . Alors $G$ est connexe si et seulement si tous les coefficients de la matrice

$I_{n} + A + A^{2} + \dots + A^{n - 1}$

sont strictement positifs.

Démonstration

Le coefficient $(i, j)$ de cette somme compte les chemins de $i$ à $j$ de longueur $0$ , $1$ , …, $n - 1$ . Il est strictement positif exactement lorsqu'il existe un chemin de $i$ à $j$ de longueur au plus $n - 1$ .

Il reste à voir qu'un chemin de $i$ à $j$ , s'il en existe, peut toujours être choisi de longueur au plus $n - 1$ . Prenons-en un de longueur minimale : s'il repassait deux fois par un même sommet, on pourrait supprimer la portion comprise entre les deux passages et obtenir un chemin plus court, ce qui contredirait la minimalité. Ce chemin visite donc des sommets deux à deux distincts : il en emprunte au plus $n$ , donc au plus $n - 1$ arêtes.

AttentionLa longueur

n - 1

n'est pas décorative

S'arrêter à $A^{2}$ ou $A^{3}$ ne prouve rien : dans un graphe en chaîne à $6$ sommets, aller du premier au dernier demande $5$ arêtes. C'est le nombre de sommets qui borne la longueur utile, pas l'intuition.

3.5 Un mot sur l'analyse des réseaux sociaux

iRemarqueHors programme, mais éclairant

Le programme signale quelques mesures utilisées pour analyser un réseau, en précisant qu'elles ne sont pas exigibles. Elles montrent bien ce qu'un graphe permet de lire.

Le degré de centralité d'un sommet est son degré, éventuellement rapporté à $n - 1$ . Un sommet de fort degré est directement connecté à beaucoup d'autres — un « influenceur » au sens le plus naïf.
Le degré d'intermédiarité mesure la fréquence à laquelle un sommet se trouve sur le chemin le plus court entre deux autres. Un sommet peut avoir peu de voisins et une intermédiarité énorme : c'est le pont entre deux communautés, celui dont le retrait coupe le réseau en deux.

Ces deux mesures ne classent pas les sommets dans le même ordre, et c'est tout l'intérêt : « être connecté » et « être incontournable » ne sont pas la même chose.

Python : Compter les chemins, tester la connexité

Une fois le graphe rangé dans un tableau, tout devient du calcul matriciel.


import numpy as np

A = np.array([[0,1,0,0,1],
              [1,0,1,0,1],
              [0,1,0,1,0],
              [0,0,1,0,1],
              [1,1,0,1,0]])
n = A.shape[0]

print(np.linalg.matrix_power(A, 2))   # chemins de longueur 2
print(np.diag(A @ A))                 # les degres : [2 3 2 2 3]

S = np.eye(n, dtype=int)
P = np.eye(n, dtype=int)
for d in range(1, n):
    P = P @ A
    S = S + P
print("connexe :", (S > 0).all())     # True

La boucle s'arrête à $n - 1$ , conformément au théorème. Aller plus loin ne changerait rien ; s'arrêter plus tôt pourrait conclure à tort.

3.6 L'essentiel du chapitre

Fiche de synthèse

Vocabulaire : sommets, arêtes, adjacence ; orienté ou non ; degré d'un sommet.
Euler : $\sum_{s} de g (s) = 2 m$ — donc le nombre de sommets de degré impair est pair.
Matrice d'adjacence : $a_{ij} = 1$ s'il y a une arête ; symétrique $⟺$ graphe non orienté.
Théorème des puissances : $(A^{d})_{ij}$ est le nombre de chemins de longueur $d$ de $i$ à $j$ . Pour un graphe non orienté, $(A^{2})_{ii} = de g (i)$ .
Connexité : $G$ connexe $⟺$ tous les coefficients de $I_{n} + A + \dots + A^{n - 1}$ sont $> 0$ . La borne $n - 1$ vient de ce qu'un chemin minimal ne repasse jamais par un sommet.
Réseaux sociaux : centralité (degré) et intermédiarité (être sur les chemins courts) ne classent pas pareil. Non exigibles.

Continuer sur Adloun : animation, QCM, fiches, exercices