Que sait-on compter sur un graphe ? Partie 2

Motifs et polygones

Piste rouge Le 4 octobre 2020  - Ecrit par  Pierre-Louis Giscard Voir les commentaires

Dans la première partie de ce trio d’articles sur les chemins, nous avons vu comment l’analyse mathématique des réseaux du monde qui nous entourent porte de nombreux fruits à peu de frais ! Fort de nos succès, nous tentons dans cet article d’aller plus loin en posant des questions plus subtiles portant sur les motifs dans les graphes.

Lorsque nous avions analysé le réseau formé par les relations entre tribus en Papouasie Nouvelle-Guinée nous avions demandé à regarder les triangles de ce graphe, une question finalement assez subtile (comment les trouver tous ?). C’est une première étape dans l’étude d’une grande famille de cycles et chemins un peu spéciaux dont les triangles font partie : les objets auto-évitants.

Définitions : Dans un graphe, un chemin qui ne visite jamais deux fois le même nœud est appelé chemin simple ou chemin auto-évitant.

Un cycle qui ne repasse jamais par le même nœud (hormis pour revenir à son point de départ à la dernière étape !) est appelé polygone auto-évitant. Un triangle en est un bon exemple, mais aussi un carré, un pentagone, etc.

La question la plus simple que l’on peut poser concernant cette famille est sans doute de la dénombrer : combien y a-t-il de polygones auto-évitants dans un graphe ? Pour faciliter l’analyse, comme dans la première partie, nous considérons uniquement les graphes simples, pour lesquels il y a toujours soit une soit zéro arête entre deux nœuds, ces arêtes ne sont pas dirigées et il n’y a aucune arête allant d’un nœud à lui-même (pas de boucle).

Les problèmes commencent

Comptons les triangles pour commencer, c’est facile ! Dessinez un graphe simple et essayez de faire des cycles de longueur 3 pour voir ce qui se passe. Attention il faut revenir au point de départ en empruntant 3 arêtes. Vous pouvez repasser plusieurs fois par le même nœud ou par la même arête si ça vous chante...

On s’aperçoit que, dans un graphe simple, les seuls cycles de longueur $\ell=3$ sont des triangles ! Donc en comptant les cycles de longueur 3 et en divisant ce résultat par 6 on a tous les triangles.

Pourquoi diviser par 6 ?

Chaque triangle peut être parcouru dans exactement deux directions, par exemple $1\to2\to 3\to 1$ et $1\to 3\to 2\to 1$, qui sont bien deux cycles différents. Il y a donc effectivement deux fois plus de cycles de longueur 3 que de triangles. En outre, les cycles de longueur 3 sont les chemins de longueur 3 allant d’un nœud à lui même, et donc en sommant sur tous les nœuds du graphe chaque triangle est compté 3 fois. Il y ainsi exactement $6=2\times 3$ (orientation et point de départ) fois plus de cycles de longueur 3 que de triangles.

Avec le formalisme des matrices, que nous verrons en partie 3, et notre observation reliant cycles et triangles, on peut compter ces derniers avec une jolie formule :
\[ \mathcal{N}_{\text{Triangles}} = \frac{1}{6} \text{Tr}(A_G^3) \]
où $\mathcal{N}_{\text{Triangles}}$ est le nombre de triangles et $ \text{Tr}(A_G^3)$ est un nombre que l’on calcule directement à partir d’une matrice $A_G$ représentant le graphe $G$ sur lequel on dénombre les triangles. Ce qui compte pour le moment ici, c’est que cette formule comporte un unique terme.

Continuons ! Par exemple, il est possible de trouver une formule comptant les carrés dans un graphe à partir des chemins (celle-ci est donnée et expliquée dans la partie 3 de cet article). Or, cette formule comporte, nous le verrons, trois termes à calculer. C’est parce que contrairement au cas des triangles, parmi les cycles de longueur $\ell=4$ il n’y a pas que des carrés (par exemple le cycle $1\to2\to 1\to 2\to1$ est bien de longueur $4$ mais n’est pas un carré). Les termes supplémentaires de la formule enlèvent ces objets du décompte pour ne laisser que les carrés. Trois termes au total, ça reste calculable.

Par contre, si nous continuons de cette manière pour compter les pentagones, puis les hexagones et ainsi de suite, la taille de la formule qu’il nous faut évaluer augmente très vite. Par exemple, pour compter les décagones, qui ont dix côtés, nous obtenons une formule comprenant 160 termes tandis que pour les dodécagones (qui ont douze côtés) nous arrivons à une formule présentant déjà 958 termes...

Taille des formules permettant de compter les polygones d’un graphe en fonction de leur longueur. Attention l’axe des ordonnées est en échelle logarithmique ! Données disponibles sur l’encyclopédie des suites d’entiers, A081809.

Clairement, cette inflation du nombre de termes n’augure rien de bon sur le problème qui nous intéresse. Et en effet, pour compter les icosagones (20 côtés) par le même type de raisonnement il nous faudrait une formule avec plusieurs millions de termes ! Si nous changeons la question et essayons de compter les chemins auto-évitants, c’est à dire qui commencent et se terminent en des nœuds différents et qui ne repassent jamais deux fois sur le même nœud, c’est encore pis. Nos arguments nous amènent à une formule pour compter de tels chemins de longueur 10 (donc comparables aux décagones) comptant déjà 4556 termes, quant aux chemins auto-évitants de longueur 12 (comparables aux dodécagones), ils nécessitent une formule comportant presque 70000 termes. Peut-être devrions nous revoir complètement le raisonnement qui nous a conduit là ?

Dans un graphe, compter tous les icosagones comme celui montré ci-dessus est assez difficile. Il existe bien une formule mathématique utilisant des matrices pour ce faire, mais elle compte des millions de termes !

En fait, le problème du dénombrement des polygones ou des chemins auto-évitants d’un graphe est bel et bien très difficile, de sorte que la difficulté augmente exponentiellement avec la longueur des polygones ou des chemins auto-évitants que l’on cherche à dénombrer. En outre, il y a de bonnes raisons de penser qu’il n’existe pas de raisonnement franchement meilleur que celui que nous avons utilisé.
C’est un contraste saisissant avec le problème du dénombrement de tous les chemins ou cycles sur un graphe quelle que soit la longueur, que nous avions abordé en partie 1 et sur lequel nous reviendrons en dernière partie.

Remarque : À la difficulté théorique exposée ci-dessus s’ajoute une difficulté pratique lorsqu’on essaye d’analyser concrètement un graphe correspondant à un système complexe réel. En effet, les formules permettant de compter par exemple les triangles ou les carrés prennent du temps à calculer, quand bien même elles sont théoriquement compactes. Plus précisément, le nombre d’opérations élémentaires (additions et multiplications d’entiers) qu’il faut effectuer pour calculer un seul terme d’une de ces formules croît comme le cube du nombre de nœuds dans le graphe. Imaginez la difficulté que cela représente sur un graphe comme celui des liens d’amitié sur Facebook, qui comporte plus d’un milliard de nœuds !

Problèmes ouverts

Puisque le problème général du dénombrement des polygones semble particulièrement difficile, peut-être pouvons-nous le résoudre dans un cadre plus restreint. Pour cela, considérons uniquement les graphes pour lesquels tous les nœuds sont identiques, c’est à dire indistinguables (ils ont donc tous le même degré, le même nombre de seconds voisins, participent au même nombre de triangles etc., toutes les quantités auxquelles nous pourrions penser sont identiques). Ceci permet notamment de fixer un nœud de départ pour les polygones sans que le choix soit arbitraire puisqu’on arrivera toujours au même résultat.

En outre, dans l’espoir de simplifier encore les choses, demandons à ce que ce graphe soit planaire, c’est à dire que nous pouvons le dessiner sur une feuille sans qu’aucune paire d’arêtes ne se croise. Dans le même esprit, considérons les graphes infinis les plus simples ayant ces propriétés, souvent appelés réseaux. Voici le genre de chose que nous obtenons :

L’image en tête de l’article représente un polygone auto-évitant sur le réseau carré :

Pour plus de clarté, l’image ci-dessus ne montre que les arêtes parcourues par le polygone auto-évitant, pas celles du réseau carré sous-jacent.

Depuis que le problème du dénombrement de ces objets a été posé en 1947, à partir d’une question de chimie portant sur les polymères, les mathématiciens ne savent toujours pas y répondre. À défaut, nous pouvons compter les polygones auto-évitants directement avec nos ordinateurs en fixant un même nœud de départ pour ceux-ci. Voici quelques résultats obtenus de cette manière, en prenant pour exemple le réseau carré :

Longueur $\ell$ $\ell=4$ $\ell=6$ $\ell=8$ $\ell=10$ $\ell=12$ $\ell=14$ $\ell=16$
$\mathcal{N}(\ell)$ 8 24 112 560 2976 16464 94016
Longueur $\ell$ $\ell=18$ $\ell=20$ $\ell=22$ $\ell=24$ $\ell=26$ $\ell=28$ $\ell=30$
$\mathcal{N}(\ell)$ 549648 3273040 19781168 121020960 748039552 4664263744 29303071680
Nombre de polygones auto-évitants sur le réseau carré [1].

Vous pouvez trouver le nombre de polygones auto-évitants pour de plus grandes longueurs sur l’encyclopédie des suites d’entiers, numéro A010566 et A284869 pour le réseau triangulaire. Que dire ? Tout d’abord remarquons qu’il n’y a aucun polygone de longueur impaire sur le réseau carré. En fait, il n’y a aucun cycle de longueur impaire sur ce réseau (essayez d’en trouver !). C’est une conséquence de ce que le réseau carré est biparti, c’est à dire que l’on peut colorier ses nœuds en deux couleurs de manière alternée :

Le réseau carré est biparti

Cliquez ici pour voir pourquoi un graphe biparti ne peut avoir de cycle de longueur impaire.

Considérons un graphe biparti et colorons ses nœuds en deux couleurs ${\color{red}{\text{Rouge}}}$ et ${\color{blue}{\text{Bleu}}}$ comme dans l’image ci-dessus du réseau carré. Imaginons qu’il existe un cycle de longueur impaire sur ce graphe. Prenons un nœud sur ce cycle (disons un ${\color{red}{\text{Rouge}}}$ mais vous pourriez prendre ${\color{blue}{\text{Bleu}}}$ sans rien changer à l’argument). À partir de ce nœud, parcourons le cycle et notons les couleurs de nœuds que nous rencontrons en ne nous arrêtant que lorsqu’on revient sur le nœud de départ. Puisque le graphe est biparti, nous trouvons nécessairement une alternance de couleurs ${\color{red}{\text{R}}}$-${\color{blue}{\text{B}}}$-${\color{red}{\text{R}}}$-${\color{blue}{\text{B}}}$.... Si la longueur du cycle est impaire, la dernière arête est donc nécessairement entre noeuds de la même couleur, ce qui est impossible sur un graphe biparti, où une telle arête n’existe pas. Par exemple, un triangle 1-2-3-1 donnerait ${\color{red}{\text{R}}}$-${\color{blue}{\text{B}}}$-${\color{red}{\text{R}}}$-${\color{red}{\text{R}}}$, l’arête 1-3 ${\color{red}{\text{R}}}$-${\color{red}{\text{R}}}$ ne pouvant exister sur un graphe biparti.

Hormis cette observation assez simple, jusqu’à présent, personne n’a trouvé de formule donnant exactement les chiffres ci-dessus (et ceux d’après, visible sur A010566). Si vous en avez une, vous avez fait une (grande) découverte ! C’est un problème totalement ouvert :

Problèmes ouverts : Combien y a-t-il de polygones auto-évitants de longueur $\ell$ sur le réseau carré ? Et sur les réseaux hexagonal, triangulaire et de Kagomé ?

Le problème est très, très difficile et hors de portée de la combinatoire moderne.

Puisque compter exactement les polygones auto-évitants est difficile, peut-être devrions nous demander uniquement une approximation de leur nombre $\mathcal{N}(\ell)$ lorsque leur longueur $\ell$ tend vers l’infini, ce que l’on dénote $\ell \to\infty$. Cette question est triviale pour un graphe fini : il existe exactement 0 polygones auto-évitants de longueur $\ell$ quand $\ell \to\infty$. En effet, un tel graphe n’ayant qu’un nombre $N$ fini de nœuds, le plus long polygone auto-évitant est au plus de longueur $N$ et il n’en n’existe plus aucun de longueur $\ell>N$.
Donc restons dans le cas des réseaux comme ci-dessus, où le nombre de polygones de longueur $\ell$ quand $\ell \to\infty$ reste inconnu.

Eh bien nous verrons dans la partie 3 que même la question de comprendre ce que fait le nombre $\mathcal{N}(\ell)$ quand $\ell$ tend vers l’infini est l’objet d’une conjecture. Et cette conjecture est assez surprenante : elle dit que quand $\ell\to\infty$, $\mathcal{N}(\ell)$ se comporte, à peu de choses près, de la même manière quel que soit le réseau : carré, hexagonal, triangulaire, de Kagomé etc. Et bien sûr, personne ne sait le prouver...

Post-scriptum :

Je remercie Shalom Eliahou et Bruno Martin qui m’ont proposé d’écrire un article dans Images des mathématiques, article qui en est devenu 3... Je remercie également Clément Caubel et Édouard Cidrolin pour leur relecture attentive de cet article !

Article édité par Shalom Eliahou

Notes

[1Ici nous avons gardé le facteur d’orientation, c’est à dire que par exemple les carrés $1\to2\to3\to4\to1$ et $1\to4\to3\to2\to1$ comptent comme deux polygones différents. Divisez les nombres par 2 pour enlever ce facteur.

Partager cet article

Pour citer cet article :

Pierre-Louis Giscard — «Que sait-on compter sur un graphe ? Partie 2» — Images des Mathématiques, CNRS, 2020

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?