Graphes Finis et Infinis Expliqués

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. La définition n'a jamais dit fini

Revenez à la définition du guide sur les sommets et arêtes et lisez ce qu'elle dit vraiment :

G = (V, E)      with   E ⊆ [V]²

Un ensemble de sommets et un ensemble de parties à 2 éléments de celui-ci. Rien là-dedans ne parle de taille. V peut être les quatre terres de Königsberg, les entiers, les réels ou l'ensemble de toutes les chaînes binaires finies, et la définition ne bronche pas. Un graphe infini est simplement un graphe dont l'ensemble des sommets est infini, et tout le sujet de cet article est ce qui cesse discrètement de fonctionner dans ce cas.

Ce n'est pas un raffinement moderne. Le tout premier livre de théorie des graphes est Theorie der endlichen und unendlichen Graphen de Dénes König, paru en 1936, dont le titre se traduit par Théorie des graphes finis et infinis. Les graphes infinis font partie de la discipline depuis son premier manuel, et Graph Theory de Diestel leur consacre toujours un chapitre entier.

L'essentiel est de remarquer que « fini » est une hypothèse que vous utilisiez sans la voir. La plupart des énoncés des manuels sont de la forme « soit G un graphe fini », et la plupart des techniques de démonstration classiques en ont discrètement besoin :

• La récurrence sur le nombre de sommets a besoin d'un nombre de sommets sur lequel raisonner.
• Les arguments extrémaux (« prenez le sommet de degré maximum », « prenez le plus long chemin ») ont besoin que le maximum ou le plus long existe.
• Les arguments de comptage ont besoin que les comptes soient des nombres finis et non des cardinaux.
• La terminaison d'un algorithme a besoin que la recherche épuise le graphe.

Retirez la finitude et chacun de ces outils doit être remplacé par autre chose. Ce qui les remplace, dans presque tous les cas, c'est la compacité : l'idée qu'un énoncé sur un objet infini peut parfois s'assembler à partir d'énoncés sur tous ses morceaux finis. Les sections 5 et 6 présentent les deux théorèmes classiques qui font exactement cela.

2. Quelle taille : dénombrable, non dénombrable, localement fini

« Infini » n'est pas une seule taille, et trois mesures distinctes comptent. Les confondre est la première source de confusion.

Un graphe est localement fini quand chaque sommet est de degré fini. C'est une condition vraiment indépendante de la dénombrabilité, et les deux se combinent des quatre façons possibles :

• Le double rayon, un chemin infini dans les deux directions, est dénombrable et localement fini : tous les degrés valent 2.
• La grille carrée infinie sur ℤ² est dénombrable et localement finie : tous les degrés valent 4. C'est le graphe sur lequel vivent réellement un tableur, un automate cellulaire ou un monde de jeu en tuiles.
• Une étoile infinie, c'est-à-dire un centre relié à une infinité dénombrable de feuilles, est dénombrable mais pas localement finie : le centre est de degré infini.
• Le graphe complet sur un ensemble non dénombrable de sommets est non dénombrable et pas localement fini.
• Une famille non dénombrable de doubles rayons disjoints est non dénombrable et pourtant localement finie : il y a une infinité non dénombrable de sommets, et chacun reste de degré 2. C'est la quatrième combinaison, et elle montre qu'aucune des deux conditions n'implique quoi que ce soit sur l'autre.

Une conséquence mérite d'être énoncée car elle piège souvent : un graphe localement fini peut tout de même être infini, et un graphe infini peut n'avoir que de petits degrés. La finitude locale borne chaque sommet individuellement ; elle ne dit rien de la taille du graphe.

3. Ce que la finitude vous apportait sans le dire

Voici l'inventaire honnête. Ce sont des résultats et des techniques classiques, et chacun échoue sur les graphes infinis pour une raison précise.

Deux lignes méritent un commentaire immédiat, car ce sont celles qui surprennent le plus.

« Un sommet atteint le degré maximum » est faux, et pour la raison la plus banale de l'analyse : un ensemble infini d'entiers naturels n'a pas forcément de plus grand élément. Construisez un graphe dont les sommets ont les degrés 1, 2, 3 et ainsi de suite sans borne, et la quantité Δ(G) n'est tout simplement pas définie. Tout argument extrémal qui commence par « soit v un sommet de degré maximum » a donc supposé discrètement la finitude, ou au moins une borne.

L'étoile infinie casse le lemme de König, et c'est pourquoi la finitude locale figure dans son énoncé. L'étoile est infinie et connexe, mais son plus long chemin est de longueur 2 : feuille, centre, feuille. Elle ne contient aucun rayon. Un seul sommet de degré infini suffit à détruire la conclusion, ce qui montre que l'hypothèse fait un vrai travail et n'est pas une simple précaution technique.

4. Un contre-exemple en une ligne au corollaire des poignées de main

Le lemme des poignées de main est le plus ancien théorème de la discipline, et son corollaire est celui dont tout le monde se souvient : le nombre de sommets de degré impair est pair. Sur les graphes infinis, il est faux, et le contre-exemple se dessine en une ligne.

Prenez le rayon : sommets v0, v1, v2, … avec une arête entre deux sommets consécutifs.

v0 ── v1 ── v2 ── v3 ── v4 ── ⋯

deg(v0) = 1        impair
deg(vi) = 2        pair, pour tout i ≥ 1

sommets de degré impair : exactement un.  Le corollaire fini dit que leur nombre doit être pair.

Il vaut la peine de préciser ce qui survit, car la réponse est plus intéressante qu'un simple « c'est faux ».

Cette équation ∑ deg(v) = 2|E| ne devient pas fausse ; elle devient vide. Les deux membres sont des nombres cardinaux, et pour un cardinal infini κ on a 2κ = κ, donc l'identité est vraie trivialement et n'apprend rien. Ce qui casse vraiment, c'est le raisonnement de parité construit dessus. Ce raisonnement découpe une somme finie en parties impaire et paire et conclut que la partie impaire a un nombre pair de termes, et c'est la finitude de la somme, non l'équation, qui rend cette étape légitime.

La leçon se généralise : quand un théorème fini échoue sur des graphes infinis, ce n'est généralement pas l'énoncé qui casse mais la technique de démonstration, et cette technique est généralement le comptage.

5. Le lemme de l'infini de König : le premier pont

Si la plupart des démonstrations reposent sur la finitude, la question intéressante est de savoir ce qui peut la remplacer. La première réponse, et la plus utile, est un lemme que König a publié en 1927, neuf ans avant son manuel.

Lemme de l'infini de König. Tout graphe infini, connexe et localement fini contient un rayon, c'est-à-dire un chemin infini v0, v1, v2, … sans sommet répété.

La démonstration est un argument des tiroirs répété une infinité de fois, et elle mérite d'être vue car sa forme revient dans toute la combinatoire infinie.

Partez d'un sommet quelconque v0. Le graphe est infini et connexe, donc une infinité de sommets sont accessibles depuis lui. Le graphe est localement fini, donc v0 n'a qu'un nombre fini de voisins. Supprimer v0 répartit cette infinité de sommets restants entre un nombre fini de morceaux, donc par le principe des tiroirs au moins un morceau est infini. Entrez-y, et vous voilà exactement dans la situation de départ. En répétant indéfiniment, on obtient v0, v1, v2, …, et comme chaque étape entre dans une région pas encore visitée, aucun sommet ne se répète.

Les deux hypothèses font un vrai travail, et retirer l'une ou l'autre tue la conclusion :

• Sans finitude locale, l'étoile infinie est un contre-exemple : infinie, connexe, et son plus long chemin a 3 sommets.
• Sans infinitude, il n'y a rien à démontrer.

Le lemme dépasse largement la théorie des graphes. Sous sa forme arborescente, « un arbre infini à branchement fini possède une branche infinie », il est le cœur combinatoire des arguments de compacité en logique, et c'est lui qui permet de conclure qu'un calcul ayant une infinité d'états finis doit avoir une exécution infinie. C'est la même idée qui sous-tend le théorème de compacité de la logique propositionnelle, d'où vient la section suivante.

6. De Bruijn et Erdős : la coloration se transmet

Le second grand pont prend une propriété vérifiable sur des morceaux finis et l'étend au graphe infini tout entier.

Théorème de De Bruijn-Erdős (1951). Pour un k fini, un graphe infini est k-coloriable si et seulement si chacun de ses sous-graphes finis est k-coloriable.

Le sens « seulement si » est trivial : une coloration du graphe entier se restreint à chaque sous-graphe. Le contenu est dans l'autre sens, et il est vraiment surprenant. Il dit que la colorabilité, contrainte globale portant sur une infinité de sommets à la fois, est entièrement déterminée par ce qui se passe sur des fenêtres finies. Rien de nouveau ne peut mal tourner « à l'infini ».

Deux réserves qui comptent, et que les présentations grand public omettent souvent :

• Le nombre de couleurs doit être fini. Le théorème porte sur un k fini fixé. Il ne dit pas qu'un graphe dont tous les sous-graphes finis sont coloriables avec un nombre fini de couleurs est lui-même coloriable avec un nombre fini de couleurs.
• Il exige un principe de choix. Les démonstrations classiques passent par le théorème de Tychonoff pour les espaces séparés compacts, le lemme de Zorn ou le lemme de l'ultrafiltre. Dans la théorie des ensembles de Zermelo-Fraenkel sans aucune forme de choix, le théorème n'est pas démontrable. De Bruijn et Erdős travaillaient avec l'axiome du choix, comme presque tout le monde.

La lecture pratique pour qui modélise un système non borné : si votre contrainte s'exprime comme une coloration avec une palette finie fixée, vous pouvez la vérifier sur des fragments finis et la conclure pour le tout. C'est exactement la licence que donne un argument de compacité, et c'est pourquoi la vérification de modèles finie peut parfois dire quelque chose sur des exécutions non bornées.

7. Rayons, doubles rayons et bouts

La théorie des graphes finis n'a pas de vocabulaire pour « à quoi ressemble le graphe au loin », car un graphe fini n'a pas de lointain. La théorie des graphes infinis en a besoin, et la construction classique est due à Halin.

• Un rayon est un chemin infini dans un sens v0, v1, v2, …. Le lemme de König dit que tout graphe infini, connexe et localement fini en possède un.
• Un double rayon est un chemin infini dans les deux sens, indexé par tout ℤ. C'est un arbre infini sans aucune feuille, ce qu'aucun arbre fini ne peut être.
• Un bout est une classe d'équivalence de rayons, deux rayons étant équivalents quand aucun ensemble fini de sommets ne les sépare. Les bouts sont la réponse formelle à la question « dans combien de directions distinctes ce graphe file-t-il vers l'infini ».

La notion se saisit mieux par des exemples que par la définition :

La ligne de la grille est la plus instructive. Intuitivement, un plan file dans toutes les directions, on s'attendrait donc à beaucoup de bouts, mais la définition demande si des rayons peuvent être séparés en retirant un nombre fini de sommets, et dans une grille ils ne le peuvent pas : en allant assez loin, on peut toujours contourner n'importe quel trou fini. Un seul bout est la bonne réponse, et c'est la définition, non le dessin, qui en décide.

8. Arbres couvrants et axiome du choix

Tout graphe fini connexe possède un arbre couvrant, et la démonstration est un argument glouton de deux lignes : supprimez une arête située sur un cycle jusqu'à ce qu'il n'en reste plus. Cela termine car il y a un nombre fini d'arêtes.

L'énoncé infini reste vrai, mais pour une raison différente et bien plus profonde :

Tout graphe connexe possède un arbre couvrant. Pour les graphes infinis, cela exige l'axiome du choix, et l'énoncé lui est même équivalent.

La démonstration usuelle applique le lemme de Zorn à la famille des sous-graphes acycliques ordonnée par inclusion, ce qui est un principe de choix déguisé. Que l'implication aille dans les deux sens, de sorte que « tout graphe connexe possède un arbre couvrant » ne soit pas seulement une conséquence du choix mais aussi fort que lui, est un résultat vraiment frappant : un énoncé d'apparence anodine sur les graphes se révèle être l'une des nombreuses formes équivalentes d'un axiome de la théorie des ensembles.

La portée pratique est faible et la portée conceptuelle est grande. Aucun algorithme que vous écrirez n'en sera affecté, car les graphes que manipule un programme sont finis ou au moins présentés de façon calculable. Mais cela marque précisément l'endroit où la théorie des graphes infinis cesse d'être de la combinatoire pour devenir de la théorie des ensembles, et cela explique pourquoi les ouvrages sur les graphes infinis précisent soigneusement les principes de choix qu'ils admettent.

Le même schéma se retrouve ailleurs. Plusieurs énoncés routiniers pour les graphes finis dépendent, dans leur version infinie, du choix, ou sont indépendants des axiomes de base, et c'est pourquoi De Bruijn-Erdős porte aussi une hypothèse de choix.

9. Le graphe de Rado : un graphe pour les gouverner tous

Les graphes infinis ne sont pas simplement des graphes finis avec davantage de tout. Certains se comportent de façons sans aucun équivalent fini, et l'exemple le plus net est le graphe de Rado.

On dit qu'un graphe dénombrable a la propriété d'extension si, pour toute paire d'ensembles finis disjoints de sommets U et W, il existe un sommet relié à tous les sommets de U et à aucun de W. Alors :

Unicité. Deux graphes dénombrables quelconques ayant la propriété d'extension sont isomorphes. Il existe, à isomorphisme près, exactement un tel graphe : le graphe de Rado, aussi appelé graphe aléatoire R.

Et la raison de ce nom de graphe aléatoire est la seconde moitié de l'histoire. Erdős et Rényi ont montré que si l'on construit un graphe infini dénombrable en décidant chaque arête possible indépendamment avec probabilité 1/2, le résultat satisfait la propriété d'extension avec probabilité 1. Donc :

Lancez une pièce équilibrée pour chaque paire de sommets d'un ensemble infini dénombrable.
Avec probabilité 1, le graphe obtenu est le graphe de Rado.
Recommencez, autrement. Vous obtenez à nouveau le graphe de Rado, à isomorphisme près.

Il existe essentiellement un seul graphe aléatoire infini dénombrable. Rien de comparable n'arrive aux graphes finis, où les graphes aléatoires à n sommets sont extrêmement variés et où les questions intéressantes portent toutes sur les propriétés vraies avec forte probabilité. Le graphe de Rado contient en outre tout graphe fini et tout graphe dénombrable comme sous-graphe induit, ce qui le rend universel pour les graphes dénombrables.

Pour le praticien, l'intérêt n'est pas la construction elle-même mais l'avertissement qu'elle porte : les intuitions calibrées sur les graphes finis ne sont pas seulement fausses quantitativement à l'infini, elles le sont qualitativement. « Aléatoire » cesse de vouloir dire « varié » et se met à vouloir dire « canonique ».

10. Quand l'infini est plus simple

Il serait raisonnable de supposer que les graphes infinis sont uniformément plus difficiles. Parfois, c'est l'inverse, et la théorie de Ramsey en est l'illustration classique.

Ramsey a démontré les deux dans son article de 1930. La version infinie est plus simple précisément parce qu'elle ne demande pas de borne : vous n'avez jamais à dire à quelle distance la structure monochromatique apparaît, seulement qu'elle apparaît. On peut extraire la version finie de la version infinie par un argument de compacité de la même famille que le lemme de König, mais les bornes obtenues sont désastreuses, et c'est pourquoi la théorie de Ramsey finie est un domaine distinct et bien plus difficile.

La morale générale : les énoncés infinis sont souvent plus nets parce qu'ils ne sont pas quantitatifs. Quand un théorème fini est difficile à cause de ses bornes, son analogue infini peut être bien plus simple et tout de même vous apprendre quelque chose d'utile.

11. Les graphes infinis en informatique

Les graphes infinis ne sont pas une fantaisie purement mathématique. Ils apparaissent constamment en informatique, généralement de façon implicite et toujours sous le même déguisement : un graphe qu'on ne construit jamais.

• Espaces d'états. Le graphe des configurations d'une machine de Turing, d'un programme à entiers non bornés ou d'un protocole à files non bornées est infini. Vérifier un tel système revient exactement à étudier un graphe infini donné par une description finie.
• Réseaux et grilles. La recherche de chemin sur une carte en tuiles non bornée, les automates cellulaires et les réseaux d'images vivent tous sur ℤ², un graphe infini localement fini.
• Arbres de jeu. L'arbre complet d'un jeu sans limite de coups est infini ; les algorithmes de recherche en explorent un préfixe fini.
• Graphes de Cayley. Un groupe infini muni d'une partie génératrice donne un graphe infini sommet-transitif, et la théorie géométrique des groupes étudie les groupes précisément à travers ces graphes et leurs bouts.
• Structures définies récursivement. Le graphe de toutes les chaînes finies pour l'opération « ajouter un caractère » est un arbre infini, et c'est l'objet auquel on applique le plus souvent le lemme de König en calculabilité.

La conséquence pratique est une seule distinction nette :

Sur un graphe infini localement fini , la recherche devient semi-décidable. Un parcours en largeur depuis s trouvera un chemin vers t s'il en existe un, et tournera indéfiniment sinon. La finitude locale rend chaque niveau fini, de sorte que la recherche atteint chaque distance en temps fini. Elle peut confirmer l'accessibilité, jamais la réfuter.

Cette asymétrie explique pourquoi BFS plutôt que DFS est le bon choix sur un graphe infini : BFS explore par ordre de distance et atteint tout sommet accessible en temps fini, alors que DFS peut descendre une seule branche infinie et ne jamais revenir. C'est aussi la raison d'être de l'approfondissement itératif. Pour obtenir la terminaison, il faut quelque chose en plus : la finitude locale avec une borne, une mesure monotone décroissante, ou une abstraction finie de l'espace d'états.

12. Erreurs courantes

• Supposer qu'un maximum ou un minimum existe. « Prenez le sommet de degré maximum » et « prenez le plus long chemin » présupposent tous deux la finitude ou une borne explicite. Sur un graphe infini, ils peuvent ne désigner rien du tout.
• Utiliser le corollaire des degrés impairs. Le rayon a exactement un sommet de degré impair, comme le montre la section 4 shows.
• Faire une récurrence sur le nombre de sommets. Ce nombre n'existe pas. La récurrence transfinie est disponible, mais elle exige un bon ordre, ce qui est un autre recours au choix.
• Oublier la finitude locale dans le lemme de König. L'étoile infinie est infinie, connexe, et ne contient aucun rayon. L'hypothèse n'est pas décorative.
• S'attendre à la terminaison. La recherche sur un graphe infini est semi-décidable, donc une réponse « pas de chemin » n'arrive jamais. Bornez explicitement la recherche ou travaillez sur une abstraction finie.
• Lancer un DFS sur un graphe infini. Une seule branche infinie l'engloutit. Utilisez BFS ou l'approfondissement itératif.
• Appliquer des résultats de comptage finis. Tout ce qui est démontré en comptant sommets, arêtes ou incidences doit être réexaminé ; ce qui est démontré par compacité survit généralement.
• Traiter « infini » comme une seule chose. Dénombrable ou non et localement fini ou non sont indépendants, et presque tous les théorèmes dépendent de la combinaison que vous avez.

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. König, D. (1927). "Über eine Schlussweise aus dem Endlichen ins Unendliche." Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum (Szeged) 3, 121 à 130. Le lemme de l'infini.
2. Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30, 264 à 286. Contient les théorèmes de Ramsey fini et infini.
3. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig : Akademische Verlagsgesellschaft. Le premier livre de théorie des graphes, dont le titre nomme déjà les deux cas.
4. de Bruijn, N. G. and Erdős, P. (1951). "A Colour Problem for Infinite Graphs and a Problem in the Theory of Relations." Indagationes Mathematicae 13, 369 à 373.
5. Erdős, P. et Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14, 295 à 315. Contient l'observation que le graphe aléatoire dénombrable est déterminé à isomorphisme près.
6. Halin, R. (1964). "Über unendliche Wege in Graphen." Mathematische Annalen 157, 125 à 137. La théorie des bouts des graphes.
7. Rado, R. (1964). "Universal Graphs and Universal Functions." Acta Arithmetica 9, 331 à 340. La construction explicite du graphe dénombrable universel.
8. Cameron, P. J. (1997). "The Random Graph." Dans R. L. Graham et J. Nešetřil (dir.), The Mathematics of Paul Erdős II, 333 à 351. Berlin : Springer. Un panorama du graphe de Rado et de ses propriétés.
9. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York : Springer.
10. West, D. B. (2001). Introduction to Graph Theory, 2e édition. Upper Saddle River : Prentice Hall.
11. Bondy, J. A. et Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. Londres : Springer.
12. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer. Le chapitre 8 est consacré aux graphes infinis, aux rayons et aux bouts.