Théorie des graphes

Un plan de métro, une liste d'amis sur un réseau social, un tableau des échanges commerciaux entre pays, l'ensemble des liens hypertextes qui relient les pages du web : ces objets n'ont apparemment rien de commun. Ils le deviennent dès que l'on efface tout sauf une information, la seule qui compte ici : qui est relié à qui. Ce qui reste alors est un ensemble de points, et un ensemble de liens entre ces points. Cet objet minimal s'appelle un graphe, et il est d'une efficacité surprenante.

L'originalité de ce chapitre est qu'un graphe se manipule dans deux langages qui disent exactement la même chose. Le premier est le dessin : des ronds et des traits, sur lesquels on lit d'un coup d'œil les voisinages et les chemins. Le second est un tableau de nombres, la matrice d'adjacence, qui contient exactement la même information sous une forme calculable. Tout l'intérêt est là : traduite en matrice, une question de dessin devient un calcul, et le calcul, vous savez le mener depuis le chapitre précédent. Le théorème central du chapitre dit ainsi que le coefficient d'indice $(i,j)$ de $A^d$ compte les chemins de longueur $d$ allant du sommet $i$ au sommet $j$. Une multiplication de matrices, et l'on connaît d'un coup tous les trajets d'une longueur donnée dans un réseau que l'on ne pourrait pas dessiner.

Le plan est le suivant. La section $1$ explique la démarche de modélisation et donne les ordres de grandeur des graphes réels. Les sections $2$ et $3$ installent le vocabulaire, d'abord sans orientation puis avec. La section $4$ construit la matrice d'adjacence et fait le lien entre ses coefficients et le dessin. La section $5$ définit les chaînes et les cycles, et la section $6$ démontre le théorème des puissances, qui est le résultat le plus utilisé du chapitre. Les sections $7$ et $8$ traitent la connexité et la distance, la section $9$ les degrés et la formule d'Euler dite des poignées de main. Les sections $10$ et $11$ sont deux compléments : les cycles eulériens, et les mesures de centralité utilisées dans l'analyse des réseaux sociaux.

Voici enfin les notations en vigueur dans tout le chapitre. Un graphe est noté $G=(S,\mathcal{A})$, où $S$ est l'ensemble de ses sommets et $\mathcal{A}$ l'ensemble de ses arêtes, ou de ses arcs s'il est orienté. Son ordre est le nombre $n$ de sommets, et $m$ désigne le nombre d'arêtes. Une arête est notée $\{u,v\}$, un arc $(u,v)$. La matrice d'adjacence est notée $A=(a_{i,j})$ : le $\mathcal{A}$ calligraphique désigne toujours l'ensemble des arêtes, le $A$ droit toujours la matrice. Le degré d'un sommet $s$ est noté $d(s)$, ses degrés entrant et sortant $d^{-}(s)$ et $d^{+}(s)$. La distance entre deux sommets est notée $\delta (u,v)$, avec la lettre delta, car $d$ est déjà pris par le degré ; l'excentricité d'un sommet est $e(s)$ et le diamètre du graphe $\mathrm{diam}(G)$. Une chaîne s'écrit $u_0-u_1-\cdots -u_k$ et un chemin orienté $u_0\to u_1\to \cdots \to u_k$. Enfin, le symbole $\square$ marque la fin d'une démonstration.

Modéliser par un graphe

Modéliser une situation par un graphe demande deux décisions, et deux seulement : que représentent les sommets, et quelle relation représentent les arêtes. Tout le reste du travail est mathématique. Ces deux décisions ne sont pas neutres : selon la relation choisie, le graphe obtenu est orienté ou non, et les conclusions changent.

Voici cinq situations classiques, avec les ordres de grandeur correspondants.

Ces ordres de grandeur méritent d'être médités. Le dernier chiffre publié par Meta pour Facebook seul, en décembre $2023$, était d'environ $3,07$ milliards de comptes actifs mensuels, ce qui donne un graphe à plus de trois milliards de sommets. Aucun chiffre officiel n'existe pour le graphe du web ; les estimations disponibles évoquent plusieurs centaines de milliards de documents indexés. Un tel graphe ne se dessine évidemment pas : il ne s'étudie que par le calcul, ce qui est exactement le propos de ce chapitre. À l'inverse, le réseau des stations d'un métro tient sur une feuille, et c'est sur des exemples de cette taille que nous apprendrons les méthodes.

La distinction orienté ou non n'est pas une subtilité d'école. L'amitié sur Facebook est symétrique : si $u$ est ami avec $v$, alors $v$ est ami avec $u$, et le graphe n'est pas orienté. L'abonnement sur un réseau du type X ou Instagram ne l'est pas : on peut suivre un compte sans être suivi en retour, et le graphe est orienté. Un lien hypertexte non plus : la page $u$ peut pointer vers $v$ sans réciprocité, ce qui est précisément ce qui permet de classer les pages par importance.

Une fois la modélisation faite, les questions que l'on pose au graphe sont toujours à peu près les mêmes. L'information circule-t-elle entre deux points quelconques du réseau, autrement dit le graphe est-il connexe ? Combien d'étapes faut-il au minimum pour aller d'un point à un autre, autrement dit quelle est la distance ? Combien existe-t-il de trajets d'une longueur donnée ? Enfin, quels sommets sont les plus importants, et en quel sens ? Ce chapitre donne un outil pour chacune de ces questions.

Vocabulaire des graphes non orientés

Le mot simple porte deux interdictions. Une arête relie deux sommets distincts : il n'y a pas de boucle, c'est-à-dire d'arête d'un sommet vers lui-même. Et $\mathcal{A}$ est un ensemble de paires : une même paire y figure au plus une fois, il n'y a donc pas d'arête multiple. Un graphe qui autorise boucles et arêtes multiples s'appelle un multigraphe ; nous n'en rencontrerons qu'un seul, à la section $10$, avec les ponts de Königsberg.

Trois familles de graphes reviennent constamment, et méritent un nom.

Graphes orientés

Lorsque la relation modélisée n'est pas symétrique, il faut munir chaque lien d'un sens.

L'arc $(u,v)$ et l'arc $(v,u)$ sont deux arcs différents. Un graphe orienté peut contenir les deux, l'un des deux, ou aucun des deux : c'est toute la différence avec le cas non orienté, où l'arête $\{u,v\}$ et l'arête $\{v,u\}$ sont la même.

À tout graphe orienté on peut associer le graphe non orienté obtenu en effaçant le sens des flèches, appelé graphe non orienté sous-jacent. C'est une opération qui perd de l'information, et il faut se garder de l'effectuer sans le dire : sur $G_2$, elle transformerait les deux arcs $(1,3)$ et $(3,1)$ en une seule arête.

Matrice d'adjacence

Pour calculer sur un graphe, il faut le ranger dans un tableau. Cela suppose d'abord de numéroter ses sommets, une fois pour toutes.

La matrice d'adjacence dépend de la numérotation choisie : changer l'ordre des sommets échange les lignes et les colonnes correspondantes. Ce n'est pas gênant, à une condition, impérative : annoncer la numérotation avant d'écrire la matrice, et ne plus en changer.

Démonstration. Pour le premier point, un graphe simple ne comporte pas de boucle : le sommet $s_i$ n'est jamais adjacent à lui-même, donc $a_{i,i}=0$ pour tout indice $i$.

Pour le second point, soient $i$ et $j$ deux indices. Dans un graphe non orienté, une arête est une paire $\{s_i,s_j\}$, et $\{s_i,s_j\}=\{s_j,s_i\}$ : les deux écritures désignent le même ensemble. L'appartenance $\{s_i,s_j\}\in \mathcal{A}$ équivaut donc à $\{s_j,s_i\}\in \mathcal{A}$. Par définition de la matrice d'adjacence, $a_{i,j}$ et $a_{j,i}$ valent tous deux $1$ dans ce cas, et tous deux $0$ dans le cas contraire. Ainsi $a_{i,j}=a_{j,i}$ pour tous $i$ et $j$, ce qui signifie exactement que ${}^{t}A=A$. $\square$

La réciproque de ce dernier point est vraie et tout aussi utile : une matrice carrée dont les coefficients sont des $0$ et des $1$, symétrique et de diagonale nulle, est la matrice d'adjacence d'un unique graphe simple non orienté sur les sommets numérotés. Une matrice non symétrique, elle, ne peut provenir que d'un graphe orienté.

Démonstration. Traitons le cas non orienté. Fixons $i$. La somme de la ligne $i$ est ${\sum }_{j=1}^n{a}_{i,j}$. Chaque terme de cette somme vaut $1$ lorsque $s_j$ est voisin de $s_i$, et $0$ sinon : la somme compte donc exactement le nombre de voisins de $s_i$, c'est-à-dire son degré. La symétrie de $A$ donne alors le résultat pour la colonne $i$, dont les coefficients sont les mêmes.

Dans le cas orienté, le même raisonnement s'applique : ${\sum }_{j=1}^n{a}_{i,j}$ compte les arcs d'origine $s_i$, soit $d^{+}(s_i)$, tandis que ${\sum }_{k=1}^n{a}_{k,i}$ compte les arcs d'extrémité $s_i$, soit $d^{-}(s_i)$.

Pour le troisième point, la somme de tous les coefficients est ${\sum }_{i=1}^n{\sum }_{j=1}^n{a}_{i,j}$, c'est-à-dire la somme des sommes de lignes. Dans le cas orienté, elle vaut donc ${\sum }_{i=1}^n{d}^{+}(s_i)$, et chaque arc étant compté une fois, à sa ligne d'origine, ce total vaut $m$. Dans le cas non orienté, chaque arête $\{s_i,s_j\}$ fournit deux coefficients égaux à $1$, à savoir $a_{i,j}$ et $a_{j,i}$ : le total vaut donc $2m$. $\square$

Chaînes, chemins et cycles

Se déplacer dans un graphe, c'est passer de proche en proche d'un sommet à un sommet voisin.

Une chaîne peut repasser par un sommet déjà visité, et même réemprunter une arête déjà parcourue. Pour tout sommet $u$, la suite réduite à $u$ est une chaîne de longueur $0$. Deux qualificatifs servent à interdire les répétitions.

Une chaîne élémentaire est toujours simple, car deux arêtes égales auraient les mêmes extrémités ; la réciproque est fausse. Dans un graphe simple, un cycle est nécessairement de longueur au moins $3$ : la longueur $1$ exigerait une boucle, et la longueur $2$ réemprunterait la même arête à l'aller et au retour.

Dans le cas orienté, les mêmes notions existent, mais chaque étape doit respecter le sens des flèches, et le vocabulaire change.

Contrairement au cas non orienté, un circuit de longueur $2$ est possible dans un graphe orienté : il suffit que les deux arcs opposés $(u,v)$ et $(v,u)$ existent, et l'on peut alors décrire $u\to v\to u$ sans réemprunter le même arc.

Démonstration. Notons $u=x_0-x_1-\cdots -x_p=v$ la première chaîne et $v=y_0-y_1-\cdots -y_q=w$ la seconde. Considérons la suite de sommets obtenue en écrivant la première, puis la seconde privée de son premier terme :

$$x_0-x_1-\cdots -x_p-y_1-y_2-\cdots -y_q.$$

Deux sommets consécutifs y sont adjacents : c'est vrai à l'intérieur de chaque morceau par hypothèse, et au raccord parce que $x_p=v=y_0$ est adjacent à $y_1$. C'est donc une chaîne, et elle comporte $p+q$ arêtes. Elle joint bien $x_0=u$ à $y_q=w$. Le même raisonnement vaut mot pour mot pour les chemins d'un graphe orienté. $\square$

Compter les chemins avec les puissances de la matrice

Voici le théorème central du chapitre. Il transforme un problème de dénombrement de trajets, qui semble exiger un examen du dessin, en un simple produit de matrices.

Démonstration. Pour tous indices $i$ et $j$ et tout entier naturel $d$, notons $N_d(i,j)$ le nombre de chemins de longueur $d$ allant de $s_i$ à $s_j$. Ce nombre est fini, car un tel chemin est déterminé par la suite de ses $d+1$ sommets, choisis parmi un ensemble fini. Montrons par récurrence sur $d$ la propriété

$$\mathcal{P}(d):\text{pour tous indices }i\text{ et }j,N_d(i,j)=(A^d{)}_{i,j}.$$

Initialisation. Traitons d'abord $d=0$. Un chemin de longueur $0$ d'origine $s_i$ se réduit au seul sommet $s_i$ : il y en a exactement un allant de $s_i$ à $s_i$, et aucun allant de $s_i$ à $s_j$ lorsque $j\ne i$. Ainsi $N_0(i,j)$ vaut $1$ si $i=j$ et $0$ sinon, ce qui est exactement le coefficient d'indice $(i,j)$ de $A^0=I_n$. Donc $\mathcal{P}(0)$ est vraie.

Hérédité. Soit $d$ un entier naturel tel que $\mathcal{P}(d)$ soit vraie. Fixons deux indices $i$ et $j$, et comptons les chemins de longueur $d+1$ allant de $s_i$ à $s_j$. Un tel chemin s'écrit

$$s_i=u_0\to u_1\to \cdots \to u_d\to u_{d+1}=s_j,$$

et il possède un avant-dernier sommet $u_d$, parfaitement déterminé par le chemin. Classons donc ces chemins selon ce sommet : pour chaque indice $k$ compris entre $1$ et $n$, notons $E_k$ l'ensemble des chemins de longueur $d+1$ de $s_i$ à $s_j$ dont l'avant-dernier sommet est $s_k$. Un chemin appartient à un et un seul de ces ensembles, qui sont donc deux à deux disjoints et de réunion l'ensemble de tous les chemins comptés.

Dénombrons $E_k$. Se donner un élément de $E_k$, c'est se donner un chemin de longueur $d$ de $s_i$ à $s_k$, puis franchir l'arc de $s_k$ vers $s_j$ ; cette dernière étape est possible si et seulement si $a_{k,j}=1$, et elle est alors unique. Donc $E_k$ est vide si $a_{k,j}=0$, et de cardinal $N_d(i,k)$ si $a_{k,j}=1$. Dans les deux cas, $\mathrm{card}(E_k)=N_d(i,k)a_{k,j}$. En sommant sur $k$,

$$N_{d+1}(i,j)=\sum _{k=1}^n{N}_d(i,k)a_{k,j}.$$

L'hypothèse de récurrence donne $N_d(i,k)=(A^d{)}_{i,k}$, d'où

$$N_{d+1}(i,j)=\sum _{k=1}^n(A^d{)}_{i,k}{a}_{k,j}=(A^{d}A{)}_{i,j}=(A^{d+1}{)}_{i,j},$$

la dernière égalité venant de la définition du produit matriciel. Donc $\mathcal{P}(d+1)$ est vraie.

Conclusion. Par récurrence, $\mathcal{P}(d)$ est vraie pour tout entier naturel $d$. $\square$

Ce théorème a plusieurs conséquences immédiates, toutes utiles en exercice.

Démonstration. Le premier point est immédiat : les chemins de longueur $d$ se répartissent selon leur couple d'extrémités $(s_i,s_j)$, et le nombre de ceux qui correspondent au couple $(s_i,s_j)$ est $(A^d{)}_{i,j}$. La somme de tous les coefficients de $A^d$ les compte donc tous, une fois chacun.

Pour le deuxième point, écrivons le coefficient diagonal du produit :

$$(A^2{)}_{i,i}=\sum _{k=1}^n{a}_{i,k}{a}_{k,i}=\sum _{k=1}^n{a}_{i,k}^2=\sum _{k=1}^n{a}_{i,k}=d(s_i),$$

où l'on a utilisé successivement la symétrie de $A$, le fait que chaque $a_{i,k}$ vaut $0$ ou $1$, donc est égal à son carré, et la propriété de la section $4$ sur la somme d'une ligne. Concrètement, les chaînes fermées de longueur $2$ issues de $s_i$ consistent à aller chez un voisin puis à revenir : il y en a autant que de voisins.

Pour le troisième point, fixons $i$ et comptons les chaînes fermées de longueur $3$ issues de $s_i$, dont le nombre est $(A^3{)}_{i,i}$. Une telle chaîne s'écrit $s_i-u-v-s_i$. Comme le graphe est simple, il n'a pas de boucle, donc $u\ne s_i$ et $v\ne s_i$ ; de plus $u$ et $v$ sont adjacents, donc distincts. Les trois sommets $s_i$, $u$, $v$ sont ainsi deux à deux distincts et deux à deux adjacents : ils forment un triangle contenant $s_i$. Réciproquement, chaque triangle contenant $s_i$ fournit exactement deux telles chaînes, correspondant aux deux sens de parcours. Donc $(A^3{)}_{i,i}=2t_i$, où $t_i$ désigne le nombre de triangles contenant $s_i$. En sommant sur $i$, et en remarquant que chaque triangle est compté une fois pour chacun de ses trois sommets,

$$\mathrm{tr}(A^3)=\sum _{i=1}^{n}2t_i=2\times 3\times T=6T,$$

où $T$ est le nombre de triangles du graphe. D'où $T=\frac{1}{6}\mathrm{tr}(A^3)$. $\square$

Connexité et composantes connexes

Un réseau n'a d'intérêt que si l'information peut y circuler. La notion correspondante est la connexité.

Démonstration. Réflexivité. Pour tout sommet $u$, la chaîne réduite au seul sommet $u$, de longueur $0$, joint $u$ à $u$. Donc $u\mathcal{R}u$.

Symétrie. Supposons $u\mathcal{R}v$ et soit $u=x_0-x_1-\cdots -x_k=v$ une chaîne. La suite obtenue en la lisant à l'envers, à savoir $x_k-x_{k-1}-\cdots -x_0$, est encore une chaîne : deux sommets consécutifs y sont adjacents, l'adjacence étant symétrique dans un graphe non orienté. Elle joint $v$ à $u$, donc $v\mathcal{R}u$.

Transitivité. Supposons $u\mathcal{R}v$ et $v\mathcal{R}w$. La propriété de concaténation de la section $5$ fournit une chaîne de $u$ à $w$, donc $u\mathcal{R}w$. $\square$

Cette relation range donc les sommets en paquets, deux sommets étant dans le même paquet exactement lorsqu'on peut aller de l'un à l'autre.

En numérotant les sommets composante par composante, la matrice d'adjacence prend une forme diagonale par blocs, chaque bloc correspondant à une composante et tous les coefficients situés hors des blocs étant nuls. C'est ce que l'on lit sur le tableau suivant, qui est la matrice d'adjacence de $G_4$ pour la numérotation $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$.

Reste à savoir tester la connexité sans examiner le dessin, ce qui est indispensable dès que le graphe est grand. Le résultat repose sur le lemme suivant, qui borne la longueur des chaînes utiles.

Démonstration. L'ensemble des longueurs des chaînes joignant $u$ à $v$ est une partie non vide de $\mathbb{N}$, puisque $u$ et $v$ sont reliés ; elle admet donc un plus petit élément. Soit $u=u_0-u_1-\cdots -u_k=v$ une chaîne de longueur minimale $k$.

Montrons par l'absurde que ses sommets sont deux à deux distincts. Supposons qu'il existe deux indices $p<q$ tels que $u_p=u_q$. Considérons alors la suite

$$u_0-u_1-\cdots -u_p-u_{q+1}-u_{q+2}-\cdots -u_k.$$

C'est encore une chaîne joignant $u$ à $v$. En effet, si $q=k$, la suite s'arrête à $u_p=u_q=v$, et tous ses couples de sommets consécutifs proviennent de la chaîne initiale ; si $q<k$, ces couples sont eux aussi inchangés, sauf au raccord, où $u_p=u_q$ est adjacent à $u_{q+1}$ par hypothèse. Dans les deux cas, la longueur obtenue vaut $k-(q-p)$, qui est strictement inférieure à $k$ puisque $q>p$. Cela contredit la minimalité de $k$.

Les sommets $u_0,u_1,\dots ,u_k$ sont donc deux à deux distincts : la chaîne est élémentaire. Ces $k+1$ sommets distincts appartiennent à $S$, qui en compte $n$, donc $k+1⩽n$, c'est-à-dire $k⩽n-1$. $\square$

Démonstration. Commençons par une remarque valable dans les deux sens. D'après le théorème des puissances, pour tous indices $i$ et $j$,

$$M_{i,j}=\sum _{d=0}^{n-1}(A^d{)}_{i,j}$$

est une somme de $n$ nombres entiers positifs ou nuls, le terme d'indice $d$ comptant les chaînes de longueur $d$ de $s_i$ à $s_j$. Par conséquent, $M_{i,j}>0$ si et seulement s'il existe au moins un entier $d$ compris entre $0$ et $n-1$ tel que $(A^d{)}_{i,j}>0$, c'est-à-dire si et seulement s'il existe une chaîne de longueur au plus $n-1$ joignant $s_i$ à $s_j$.

Supposons $G$ connexe, et soient $i$ et $j$ deux indices. Si $i=j$, alors $(A^0{)}_{i,i}=(I_n{)}_{i,i}=1$, donc $M_{i,i}⩾1>0$. Si $i\ne j$, les sommets $s_i$ et $s_j$ sont reliés par connexité ; le lemme fournit une chaîne élémentaire de $s_i$ à $s_j$, de longueur $d⩽n-1$. Alors $(A^d{)}_{i,j}⩾1$, et tous les autres termes de la somme étant positifs ou nuls, $M_{i,j}>0$. Tous les coefficients de $M$ sont donc strictement positifs.

Réciproquement, supposons tous les coefficients de $M$ strictement positifs, et soient $u$ et $v$ deux sommets, d'indices $i$ et $j$. Comme $M_{i,j}>0$, la remarque initiale fournit un entier $d$ tel que $(A^d{)}_{i,j}>0$, c'est-à-dire au moins une chaîne de longueur $d$ joignant $u$ à $v$. Ainsi deux sommets quelconques sont reliés : $G$ est connexe. $\square$

Dans le cas orienté, la même construction fonctionne, mais la propriété obtenue est plus exigeante : on parle de forte connexité, c'est-à-dire de l'existence, pour tout couple de sommets $(u,v)$, d'un chemin de $u$ vers $v$ et d'un chemin de $v$ vers $u$. Le critère est identique : le graphe orienté est fortement connexe si et seulement si tous les coefficients de $I_n+A+\cdots +A^{n-1}$ sont strictement positifs. La démonstration est la même, à ceci près que la symétrie n'est plus disponible, ce qui est sans importance puisqu'on traite les couples $(i,j)$ et $(j,i)$ séparément.

Distance, excentricité et diamètre

Cette définition a un sens : l'ensemble des longueurs de chaînes joignant $u$ à $v$ est une partie non vide de $\mathbb{N}$, elle admet donc un plus petit élément. Le lemme de la section $7$ garantit de plus que $\delta (u,v)⩽n-1$ dès que les deux sommets sont reliés. Enfin, la distance est symétrique : $\delta (u,v)=\delta (v,u)$, puisqu'une chaîne se parcourt dans les deux sens.

Démonstration. D'après le théorème des puissances, $(A^d{)}_{i,j}$ est le nombre de chaînes de longueur $d$ joignant $s_i$ à $s_j$. Dire que $(A^d{)}_{i,j}>0$, c'est donc dire qu'il existe au moins une chaîne de longueur $d$ joignant $s_i$ à $s_j$. L'ensemble $\{d\in \mathbb{N};(A^d{)}_{i,j}>0\}$ est ainsi exactement l'ensemble des longueurs de chaînes joignant $s_i$ à $s_j$, dont le plus petit élément est la distance par définition. $\square$

Démonstration. Posons $p=\delta (u,v)$ et $q=\delta (v,w)$. Il existe une chaîne de longueur $p$ de $u$ à $v$ et une chaîne de longueur $q$ de $v$ à $w$. Par concaténation, il existe une chaîne de longueur $p+q$ de $u$ à $w$. La distance de $u$ à $w$ étant la plus petite longueur d'une telle chaîne, elle est inférieure ou égale à $p+q$. $\square$

Degré d'un sommet et formule d'Euler

Dans un multigraphe, chaque arête multiple compte pour autant d'unités qu'il y a d'exemplaires, et une boucle compte deux fois, puisqu'elle est incidente deux fois au même sommet. Ce point servira aux ponts de Königsberg.

Démonstration. Elle procède par double comptage : on dénombre de deux façons différentes le même ensemble fini, ce qui force l'égalité des deux résultats.

Considérons l'ensemble $\mathcal{I}$ des couples $(s,a)$ où $s$ est un sommet, $a$ une arête, et où $s$ est une extrémité de $a$. Les éléments de $\mathcal{I}$ s'appellent les incidences du graphe.

Premier comptage, en groupant par sommet. Fixons un sommet $s$. Le nombre d'incidences dont la première composante est $s$ est, par définition même du degré, égal à $d(s)$. En sommant sur tous les sommets,

$$\mathrm{card}(\mathcal{I})=\sum _{s\in S}d(s).$$

Second comptage, en groupant par arête. Fixons une arête $a=\{u,v\}$. Le graphe étant simple, ses deux extrémités $u$ et $v$ sont distinctes, donc le nombre d'incidences dont la seconde composante est $a$ vaut exactement $2$. En sommant sur les $m$ arêtes,

$$\mathrm{card}(\mathcal{I})=\sum _{a\in \mathcal{A}}2=2m.$$

Les deux comptages portant sur le même ensemble, ${\sum }_{s\in S}d(s)=2m$. $\square$

L'énoncé porte le nom de « formule des poignées de main » pour la raison suivante : si des personnes se serrent la main, chaque poignée de main est comptée deux fois, une fois pour chaque main tendue. Le total des poignées de main données par l'ensemble des personnes est donc pair.

Démonstration. Notons $P$ l'ensemble des sommets de degré pair et $I$ celui des sommets de degré impair ; ils forment une partition de $S$, donc

$$\sum _{s\in P}d(s)+\sum _{s\in I}d(s)=\sum _{s\in S}d(s)=2m.$$

La somme ${\sum }_{s\in P}d(s)$ est paire, comme somme d'entiers pairs, et $2m$ est pair. Par différence, ${\sum }_{s\in I}d(s)$ est un entier pair.

Or cette dernière somme comporte $\mathrm{card}(I)$ termes, tous impairs. Une somme de $k$ entiers impairs a la même parité que $k$ : en effet, chaque terme s'écrit $2q_i+1$, et la somme vaut $2\left(\sum q_i\right)+k$, qui est pair si et seulement si $k$ l'est. Comme la somme est paire, $\mathrm{card}(I)$ est pair. $\square$

Démonstration. Dans $K_n$, chaque sommet est adjacent aux $n-1$ autres, donc tous les sommets sont de degré $n-1$. La somme des degrés vaut par conséquent $n(n-1)$. La formule des poignées de main donne $n(n-1)=2m$, d'où $m=\frac{n(n-1)}{2}$. $\square$

Démonstration. Chaque arc $(u,v)$ possède exactement une origine, à savoir $u$, et exactement une extrémité, à savoir $v$. En classant les arcs selon leur origine, on obtient une partition de $\mathcal{A}$ en $\mathrm{card}(S)$ paquets, celui associé à $s$ comptant $d^{+}(s)$ arcs ; d'où ${\sum }_{s\in S}{d}^{+}(s)=m$. En classant cette fois les arcs selon leur extrémité, le même argument donne ${\sum }_{s\in S}{d}^{-}(s)=m$. Les deux sommes valent $m$, donc elles sont égales. $\square$

Complément : chaînes et cycles eulériens

Cette section est un complément hors programme. Aucune de ses notions n'est exigible en tant que telle, mais elle éclaire la formule d'Euler de la section précédente, dont elle est l'application historique, et elle explique l'expression de « graphe eulérien » que le programme mentionne parmi les exemples à connaître.

Une chaîne eulérienne peut repasser par un même sommet autant de fois qu'il le faut : la contrainte porte sur les arêtes, pas sur les sommets. C'est exactement le problème du dessin « sans lever le crayon et sans repasser deux fois sur le même trait ».

Le problème est né à Königsberg, ville traversée par une rivière formant une île, et dont les quatre quartiers étaient reliés par sept ponts. La question posée aux habitants était de savoir s'il existait une promenade empruntant chacun des sept ponts exactement une fois. Euler la résolut en $1736$, et cette résolution est considérée comme l'acte de naissance de la théorie des graphes.

La modélisation est la suivante : les sommets sont les quatre quartiers, à savoir la rive nord $N$, l'île $I$, la rive sud $S$ et la rive est $E$, et chaque pont devient une arête. Comme deux ponts relient $N$ à $I$, et deux autres $S$ à $I$, l'objet obtenu est un multigraphe : c'est le seul de ce cours.

Voici l'argument, qui justifie la condition nécessaire et qu'il faut comprendre plutôt que retenir. Supposons qu'une chaîne eulérienne existe, et soit $s$ un sommet qui n'est pas une extrémité de cette chaîne. Chaque fois que la promenade arrive en $s$, elle doit en repartir, et elle le fait par une autre arête, puisqu'aucune arête ne sert deux fois. Les arêtes incidentes à $s$ se groupent donc deux par deux, une pour entrer et une pour sortir, et toutes sont utilisées puisque la chaîne est eulérienne : le degré de $s$ est pair.

Il ne reste que les deux extrémités. Si la chaîne est fermée, l'arête du tout premier départ se marie avec celle de la toute dernière arrivée, et le raisonnement précédent s'applique aussi à ce sommet : tous les degrés sont pairs. Si la chaîne n'est pas fermée, le sommet de départ possède une arête de départ non appariée, et le sommet d'arrivée une arête d'arrivée non appariée : ces deux sommets, et eux seuls, sont de degré impair.

Dans tous les cas, un graphe qui admet une chaîne eulérienne a zéro ou deux sommets de degré impair. Königsberg en a quatre, donc la promenade est impossible. La réciproque, plus délicate, est admise.

Le corollaire de la section $9$ prend ici tout son sens : le nombre de sommets de degré impair étant toujours pair, les cas « un seul sommet impair » ou « trois sommets impairs » ne peuvent pas se produire. Les deux énoncés du théorème couvrent donc tous les cas favorables.

Analyse des réseaux sociaux

Les mesures présentées ici ne sont pas exigibles : le programme précise qu'on les introduit « sur des exemples simples », pour leur interprétation. Elles répondent à une question naturelle dès qu'un graphe modélise un réseau de personnes : quels sommets sont les plus importants, et en quel sens ? Il n'y a pas une seule réponse, car « important » peut vouloir dire deux choses très différentes.

C'est la proportion des autres sommets auxquels $s$ est directement relié. Ce nombre appartient toujours à l'intervalle $[0,1]$, puisque $d(s)⩽n-1$, et il vaut $1$ exactement lorsque $s$ est adjacent à tous les autres sommets. Un sommet de fort degré de centralité a beaucoup de contacts directs : c'est la définition la plus naïve de l'influenceur.

Trois remarques sur cette définition. La somme porte sur des paires et non sur des couples : la paire $\{u,v\}$ n'est comptée qu'une fois. Le graphe étant connexe, chaque dénominateur ${\sigma }_{u,v}$ est un entier supérieur ou égal à $1$, donc la formule a bien un sens. Enfin, chaque terme appartient à $[0,1]$ : lorsque toutes les plus courtes chaînes de $u$ à $v$ passent par $s$, la paire apporte $1$ ; lorsque la moitié y passe, elle apporte $\frac{1}{2}$ ; lorsque aucune n'y passe, elle apporte $0$. Pour un graphe d'ordre $n$, le nombre de paires en jeu est $\frac{(n-1)(n-2)}{2}$, ce qui donne la valeur maximale théorique de $C_B$.

Pour départager ces trois sommets, calculons l'intermédiarité. Il faut d'abord le tableau des distances, obtenu de proche en proche.

On constate sur ce réseau que, pour chaque paire de sommets, la plus courte chaîne est unique, de sorte que tous les ${\sigma }_{u,v}$ valent $1$ : chaque paire apporte donc $0$ ou $1$, et il suffit de compter les paires dont la plus courte chaîne passe par le sommet étudié.

Le tableau final est éloquent.

Les deux mesures ne disent pas la même chose. Le degré de centralité place $C$, $D$ et $F$ à égalité : ils ont autant de contacts directs les uns que les autres. L'intermédiarité les sépare nettement, et désigne $D$ comme le sommet le plus stratégique du réseau : $9$ des $15$ paires de sommets communiquent par lui. Ce n'est pas celui qui a le plus d'amis, c'est celui qui sert de pont entre les deux groupes. Retirer $D$, ou retirer $C$, couperait le réseau en deux ; retirer $A$ ne changerait presque rien. En termes de réseau social, un fort $C_D$ signale un compte très suivi localement, un fort $C_B$ signale un compte par lequel transite l'information entre communautés, dont la disparition fragmente le réseau.

Un mot, pour finir, sur les tailles réelles. Les calculs ci-dessus ont demandé une page pour sept sommets. Un réseau social réel en compte de l'ordre de trois milliards, soit environ $4,5\times 10^{18}$ paires de sommets à examiner pour une seule intermédiarité : c'est hors d'atteinte, non seulement à la main, mais aussi par un calcul direct sur ordinateur. L'analyse des grands réseaux repose donc sur des algorithmes spécialisés et sur des méthodes d'approximation, dont le principe reste exactement celui que nous venons de voir sur sept sommets.

Ce qu'il faut retenir

Les définitions à connaître.

Les trois théorèmes exigibles.

1. Puissances de la matrice d'adjacence. Le coefficient d'indice $(i,j)$ de $A^d$ est le nombre de chemins de longueur $d$ de $s_i$ à $s_j$. Démonstration par récurrence, en découpant un chemin de longueur $d+1$ sur son avant-dernier sommet.
2. Critère matriciel de connexité. Un graphe d'ordre $n$ est connexe si et seulement si tous les coefficients de $I_n+A+\cdots +A^{n-1}$ sont strictement positifs. L'exposant $n-1$ vient du lemme : entre deux sommets reliés, il existe une chaîne élémentaire, donc de longueur au plus $n-1$.
3. Formule d'Euler, dite des poignées de main. ${\sum }_{s\in S}d(s)=2m$, par double comptage des incidences. Conséquences : le nombre de sommets de degré impair est pair, et $K_n$ a $\frac{n(n-1)}{2}$ arêtes.

Le tableau des réflexes.

Les erreurs les plus fréquentes. Confondre la longueur d'une chaîne, qui compte les arêtes, avec son nombre de sommets, qui vaut un de plus. Oublier d'annoncer la numérotation des sommets avant d'écrire la matrice d'adjacence. Écrire une matrice d'adjacence non symétrique pour un graphe non orienté. Écrire une autre somme que $I_n+A+\cdots +A^{n-1}$ dans le critère de connexité, en oubliant le terme $I_n$ ou en s'arrêtant à $A^{n-2}$ : c'est cette somme exacte, et elle seule, qui figure au théorème. Oublier que $\delta$ désigne la distance et $d$ le degré. Enfin, conclure qu'un graphe est connexe après avoir exhibé une seule chaîne : il faut relier tous les couples de sommets, ou invoquer le critère matriciel.