Des points, des liens, et presque toutes les questions qu’on peut se poser dessus.
Un graphe, c’est un ensemble de sommets et un ensemble d’arêtes reliant certains couples de sommets. Rien de plus. Ni distances, ni angles, ni coordonnées : seule compte la question « qui est relié à qui ». Cette pauvreté volontaire est une force — un réseau routier, une molécule, un carnet d’adresses, un plan de métro, un circuit électrique et un arbre généalogique deviennent le même objet, et se traitent avec les mêmes outils.
Les cinq planches vont du comptage le plus élémentaire — combien d’arêtes, quels degrés — jusqu’à une transition de phase que le hasard fabrique tout seul. Deux d’entre elles racontent une histoire précise : pourquoi une promenade dans Königsberg est impossible, et pourquoi la question presque identique de Hamilton n’a toujours pas de méthode rapide.
Le degré d’un sommet est son nombre d’arêtes. Chaque arête ayant deux extrémités, elle est comptée exactement deux fois quand on additionne tous les degrés : c’est le lemme des poignées de main, sans doute le plus ancien théorème du domaine.
Σ deg(v) = 2m — d’où : le nombre de sommets de degré impair est toujours pair.
On range le graphe dans un tableau carré : Aij = 1 si i et j sont reliés, 0 sinon. Le miracle est que Akij donne exactement le nombre de marches de longueur k allant de i à j — une multiplication de matrices remplace une énumération. Ici les deux sont faites : le produit matriciel, et le dénombrement des marches une par une.
Explorer un graphe, c’est choisir un ordre de visite. Deux ordres suffisent à presque tout. Le parcours en largeur visite d’abord tous les voisins, puis les voisins des voisins : il découvre les sommets par couches, et chaque couche est exactement l’ensemble des sommets à distance k. Le parcours en profondeur s’enfonce aussi loin qu’il peut avant de revenir sur ses pas. Cliquez un sommet pour en faire la source.
Le parcours en largeur donne les plus courts chemins gratuitement, ce que le parcours en profondeur ne fait pas. Le contrôle compare ses distances à celles de Floyd-Warshall, calculées par un tout autre chemin (triple boucle sur les sommets intermédiaires) : les deux tableaux coïncident case par case.
Un arbre est un graphe connexe sans cycle. Il a toujours exactement n − 1 arêtes : une de moins et il se casse, une de plus et il boucle. Parmi tous les arbres qui relient n points donnés, lequel a la longueur totale minimale ? Deux algorithmes très différents répondent : Kruskal trie toutes les arêtes et prend les plus courtes qui ne créent pas de cycle ; Prim fait grossir un seul morceau à partir d’un sommet. Ils ne se ressemblent pas — et ils tombent sur le même total.
Le nombre d’arbres couvrants n’est pas énuméré : c’est un déterminant. Le théorème de Kirchhoff dit qu’il suffit de retirer une ligne et une colonne à la matrice D − A et de calculer le déterminant de ce qui reste. Sur le graphe complet, il doit rendre nn−2, la formule de Cayley — 11 points, c’est déjà 2 357 947 691 arbres différents.
En 1736, Euler règle une querelle de promeneurs : la ville de Königsberg compte sept ponts, peut-on faire un tour qui emprunte chacun une fois et une seule ? Sa réponse ne regarde ni la longueur des ponts ni la forme des îles — seulement les degrés. À chaque passage par une rive, on y entre et on en sort : il faut donc un degré pair partout, sauf éventuellement au départ et à l’arrivée. Königsberg a quatre rives de degré impair. C’est mort, et cela ne dépend d’aucun essai.
Le parcours n’est pas cherché à tâtons : l’algorithme de Hierholzer le construit directement, en recollant des boucles. Le contrôle affiché ne fait pas confiance à l’algorithme — il relit la suite de sommets produite et vérifie que le multiensemble des couples consécutifs est exactement celui des arêtes du graphe.
Changeons un mot : au lieu de passer une fois par chaque arête, passons une fois par chaque sommet. La question paraît jumelle. Elle ne l’est pas. Aucun critère de degré ne la tranche, et personne ne connaît de méthode rapide : c’est l’un des problèmes NP-complets fondateurs. Ici, on cherche donc à la force brute — et l’on regarde le prix.
On relance la recherche sur K5, K6, … K10 et l’on porte le nombre de nœuds explorés en échelle logarithmique. La droite obtenue n’est pas une droite de pente constante : chaque sommet ajouté multiplie le travail par un facteur qui grandit lui-même.
Le contraste est tout le sujet : pour Euler, une lecture des degrés suffit et le coût est proportionnel au nombre d’arêtes. Pour Hamilton, la même petite figure demande déjà des centaines de milliers d’essais, et le graphe de Petersen — dix sommets, tous de degré 3, parfaitement régulier et symétrique — n’a aucun cycle hamiltonien, ce qu’aucun coup d’œil ne révèle.
Prenons n sommets et ajoutons des arêtes au hasard, une par une. Au début, de petits fragments épars. À la fin, tout est relié. Entre les deux, on pourrait croire à une montée régulière. Il n’en est rien : quand le nombre moyen de voisins c franchit la valeur 1, un morceau géant apparaît d’un coup et avale une fraction fixe du graphe. C’est une transition de phase, au sens exact du terme, et elle a une équation.
Surveillez la deuxième composante : elle grandit jusqu’au seuil, puis rétrécit. C’est la signature de la transition — au-delà de c = 1, tout ce qui est gros a déjà fusionné dans le géant.
La fraction s occupée par la composante géante est solution de s = 1 − e−cs. Cette équation n’a que la solution s = 0 tant que c ≤ 1 ; au-delà, une seconde solution apparaît et c’est elle qui l’emporte. La courbe rouge est ce calcul ; les points bleus sont des graphes tirés au sort et mesurés, sans aucune formule.
Exactement au seuil, la plus grande composante n’est ni d’une taille fixe ni proportionnelle à n : elle croît comme n2/3. Cet exposant fractionnaire est la marque des points critiques. On le mesure en tirant des graphes de tailles croissantes à c = 1 et en lisant la pente du nuage en échelle logarithmique.
Le contrôle est en bas : la même mesure refaite à c = 1,5 donne une pente proche de 1, parce qu’au-delà du seuil la composante géante est proportionnelle à n. L’exposant 2/3 n’existe qu’au point critique, et disparaît dès qu’on s’en écarte.