Théorème de Robertson-Seymour

Un célèbre exemple historique : la modélisation par Euler du problème des ponts de Königsberg.
→

→

La théorie des graphes est la discipline mathématique (et informatique) qui étudie les graphes, lesquels sont des modèles abstraits de dessins de réseaux reliant des points^{[note 1]}. Ces modèles sont constitués par la donnée de « points », appelés des sommets (en référence aux polyèdres), et de « liens » entre ces points ; ces liens, pour les graphes étudiés ici, sont symétriques (les graphes sont dits non orientés) et sont appelés des arêtes.

Un graphe ne peut pas toujours être dessiné sur une feuille de papier (ou, plus rigoureusement, dans un plan) sans que les arêtes se coupent ; quand c'est possible, le graphe est alors dit planaire. Ainsi, l'explication de l'impossibilité de l'énigme des trois maisons est que le graphe qui modélise l'énigme n'est pas planaire. En 1930, Kuratowski a obtenu une caractérisation de tous les graphes planaires, légèrement reformulée quelques années plus tard par Wagner, sous la forme d'une liste de deux graphes ne devant pas être « contenus » dans un graphe donné^{[note 2]} pour que ce dernier soit planaire.

• Les deux mineurs exclus des graphes planaires.
• 
  Le graphe complet ${\displaystyle K_{5}}$ , ayant 5 sommets et 10 arêtes.
• 
  Le graphe biparti complet ${\displaystyle K_{3,3}}$ , ayant 6 sommets et 9 arêtes.

Pour de nombreuses familles de graphes, par exemple ceux pouvant être dessinés sur la surface d'un pneu (en mathématiques, on parle de tore, et les graphes ainsi traçables sont les graphes toroïdaux), on peut se demander s'il existe une caractérisation analogue ; le théorème de Robertson-Seymour apporte une réponse affirmative. Ce théorème montre qu'un certain classement (partiel) entre les graphes possède des propriétés remarquables (c'est un bel ordre). On en déduit que pour toute famille de graphes « fermée pour les mineurs » (le sens technique exact de cette expression sera détaillé plus loin), il existe une liste finie de graphes « interdits » caractérisant cette famille. Cependant, même pour des familles simples comme celle des graphes toroïdaux, cette liste peut être très longue, et on ne connaît pas en général de méthode explicite pour la construire.

En 1930, Kazimierz Kuratowski démontrait^[1] qu'un graphe était planaire s'il ne contenait pas de sous-graphe qui soit une expansion^{[note 3]} du graphe complet K₅, ou du graphe biparti complet K_3,3^{[note 4]}.

En 1937^[2], Klaus Wagner donnait une forme analogue et d'ailleurs équivalente^[3] de ce théorème, en caractérisant ces graphes comme ne contenant ni K₅ ni K_3,3 comme « mineurs ». Cette forme permet une généralisation facile à de nombreuses familles de graphes ayant une propriété analogue^{[note 5]}, par exemple « être traçable sur un tore », c'est pourquoi le théorème des mineurs, avant sa démonstration, était connu sous le nom de conjecture de Wagner (cependant, Wagner a par la suite affirmé qu'il n'avait jamais formulé lui-même cette conjecture, et avait d'ailleurs toujours pensé qu'elle devait être fausse^[4]).

Un résultat plus faible que cette conjecture, concernant seulement les arbres, découle du théorème de Kruskal^{[note 6]}, lequel avait été conjecturé en 1937 par Andrew Vázsonyi ; il fut démontré indépendamment en 1960 par Joseph Kruskal^[5] et S. Tarkowski^[6].

Entre 1983 et 2004, Neil Robertson et Paul Seymour développèrent sur une série de vingt articles publiés dans la revue Journal of Combinatorial Theory un plan de démonstration complet consistant entre autres à réduire progressivement le cas général à des cas particuliers plus simples^{[note 7]} (ainsi, le premier de leurs articles s'intitule Mineurs : exclusion d'une forêt et donne une démonstration d'une vingtaine de pages de ce que si l'un des mineurs exclus est une forêt^{[note 8]}, le théorème est vrai^[7]), mais introduisant également de nombreux concepts et outils nouveaux, comme la théorie de la décomposition arborescente^[8]. L'ensemble de la démonstration couvre au total plus de 500 pages^{[note 9]} ; la communauté mathématique en a validé le résultat^{[note 10]}, appelé désormais théorème de Robertson-Seymour^[9], pour lequel ils reçurent en 2006 le prix Fulkerson^[8] ; ce théorème, les outils développés pour sa démonstration, et ses conséquences algorithmiques inattendues, sont généralement considérés comme parmi les plus importants de la théorie des graphes^[10].

Définitions préliminaires

Un mineur d'un graphe non orienté G est un graphe pouvant être obtenu à partir de G par une suite (éventuellement vide) de contractions d'arêtes de G, de suppressions d'arêtes de G, et de suppressions de sommets isolés de G^{[11],[note 11]}.

La relation « H est un mineur de G » (qu'on notera par la suite H ≤ G) est une relation d'ordre partiel sur l'ensemble des graphes non orientés finis, considérés à isomorphisme près^{[note 12]} (si l'on ne considère pas les graphes isomorphes comme identiques, la relation n'est plus antisymétrique, et on obtient seulement un préordre^[12]).

Un préordre est appelé un beau préordre s'il ne contient aucune suite infinie strictement décroissante (on dit que la relation de préordre est bien fondée), ni aucune antichaîne infinie, c'est-à-dire aucun ensemble infini d'éléments incomparables deux à deux ; dans le cas d'un ordre (partiel), on dit que c'est un bel ordre^{[note 13]} (cette définition généralise aux ordres partiels la notion de bon ordre définie pour les ensembles totalement ordonnés).

Énoncés du théorème

Les définitions précédentes permettent de formuler rigoureusement le

L'existence d'une suite infinie strictement décroissante étant évidemment impossible (puisque chaque mineur contient alors moins d'arêtes que le graphe précédent^[13]), ce théorème revient donc à affirmer qu'il n'y a pas d'ensemble infini de graphes deux à deux incomparables par la relation ≤ ; il convient cependant de remarquer que le théorème n'exclut nullement qu'il existe de tels ensembles finis aussi grands que l'on veut^{[note 14]}.

Utilisant la notion de graphe minimal d'un ensemble, c'est-à-dire tel qu'aucun autre graphe de l'ensemble n'en soit un mineur, on arrive à un énoncé équivalent au théorème, affirmant que dans tout ensemble de graphes, il n'y a (à isomorphisme près) qu'un nombre fini de graphes minimaux ; comme on le verra plus loin, cela revient à caractériser toute famille F « fermée pour les mineurs » par un ensemble fini S de mineurs exclus^{[note 15]}.

Dire qu'il n'existe pas d'antichaînes infinies revient, par définition, à dire que dans tout ensemble infini de graphes, il existe un couple de graphes dont l'un est un mineur de l'autre^[13] ; un résultat plus précis, et qui est en fait une propriété équivalente au théorème de Robertson-Seymour^{[note 16]}, couvre également l'impossibilité de suites infinies décroissantes, et affirme que toute suite infinie ${\displaystyle G_{i}}$ de graphes contient un couple ${\displaystyle \scriptstyle (G_{i},G_{j})}$ tel que i < j et que ${\displaystyle G_{i}}$ est un mineur de ${\displaystyle G_{j}}$ ^[14].

Éléments de la démonstration

La preuve du théorème repose sur une série de résultats publiés entre 1983 et 2004 sous le titre Graph Minors, et dont l'enchaînement est résumé dans l'article Graph Minors XX, mettant un point final à la démonstration^[15]. Tous les résultats obtenus dans cette suite de vingt articles ne sont pas nécessaires à la preuve finale^{[note 7]}, mais une rédaction complète de celle-ci demanderait encore plusieurs centaines de pages^[16] ; il est difficile ne serait-ce que d'esquisser les grandes lignes d'une démonstration aussi complexe^[17].

Les deux idées essentielles utilisées par Robertson et Seymour sont, d'une part, la notion de structuration de graphe : il s'agit de techniques consistant à décrire un graphe comme composé (le plus souvent par « recollement ») de graphes plus simples^{[note 17]} ; d'autre part, l'utilisation de considérations topologiques sur les surfaces sur lesquelles un graphe peut être plongé.

La description plus détaillée qui suit est essentiellement adaptée de celle de Reinhard Diestel^[18], qui suit assez étroitement la démonstration originale, en la simplifiant quelque peu.

• En utilisant les propriétés des beaux ordres, on se ramène d'abord à l'étude d'une famille infinie de graphes n'admettant pas le graphe complet K_n comme mineur ;
• On montre ensuite qu'il existe un ensemble fini de surfaces S_k tel que les graphes de la famille étudiée sont « presque » plongeables dans l'une des S_k^{[note 18]}, alors que K_n ne s'y plonge pas.
• La conclusion résulte alors d'un raisonnement par récurrence sur le genre des surfaces S_k (leur nombre de « trous »), la base de la récurrence étant, justement, le théorème de Wagner sur les graphes planaires : une décomposition arborescente convenable d'un graphe plongé sur une surface permet de se ramener à une surface de genre inférieur (en « comblant les trous ») sans trop modifier le graphe^{[note 19]}.

Une famille F de graphes est dite fermée (ou close) pour les mineurs (ce qui sera abrégé en famille fermée dans le reste de cet article) si chaque mineur d'un graphe de F appartient également à F^{[note 20]}. Dans le langage de la théorie des ordres, une famille fermée est donc une section commençante pour la relation « être un mineur ».

Caractérisation par mineurs exclus

Si F est une famille fermée, appelons S l'ensemble des graphes qui ne sont pas dans F (le complémentaire de F). Le théorème de Robertson–Seymour affirme l'existence d'un ensemble fini H formé des éléments minimaux de S^{[note 21]}. Ces éléments minimaux caractérisent F : les graphes de F sont exactement ceux n'admettant aucun graphe de H comme mineur^[19]. Les éléments de H sont appelés les mineurs exclus (ou interdits), ou encore les obstructions^{[note 22]}, pour la famille F.

Ainsi, les graphes planaires forment une famille fermée : les contractions et les suppressions d'arêtes d'un graphe planaire ne peuvent détruire sa planarité. Il en résulte que ces graphes peuvent être caractérisés par une famille finie de mineurs exclus, qui sont dans ce cas les deux graphes du théorème de Wagner : le graphe complet K₅ et le graphe biparti complet K_3,3.

L'existence d'une caractérisation par mineurs exclus de toutes les familles fermées est une affirmation équivalente au théorème de Robertson-Seymour. En effet, si S est un ensemble de graphes, appelons F la famille des graphes n'ayant pas de mineurs dans S. F est alors fermée, et son ensemble H de mineurs exclus est exactement l'ensemble des éléments minimaux de S (incomparables deux à deux), ce qui prouve que cet ensemble est fini^[20].

Exemples de familles fermées

Les familles de graphes (finis) suivantes^{[note 24]} sont fermées pour les mineurs, et par conséquent (d'après le théorème de Robertson–Seymour) possèdent des caractérisations par mineurs exclus (mais qu'on ne connait pas explicitement en général) :

• les forêts (les graphes qui sont des unions d'arbres disjoints) ; on remarquera que les arbres eux-mêmes ne forment pas une famille fermée, un mineur d'un arbre n'étant pas forcément connexe ;
• les graphes planaires, les graphes toroïdaux, et, plus généralement, les graphes qui peuvent être tracés sur une surface donnée^[21] ;
• les graphes qui peuvent être plongés sans entrelacement^{[note 23]} ou sans nœud dans l'espace euclidien à 3 dimensions^[21] ;
• les graphes dont certains invariants^{[note 25]}, tels que la largeur arborescente ou la taille du coupe-cycles de sommets minimum, sont bornés par une constante finie fixée^{[note 26]}.

Ensembles d'obstructions

L’ensemble des obstructions pour une famille F donnée est défini comme l'ensemble des éléments minimaux (pour la relation de mineurs) du complémentaire de F, c'est-à-dire que c'est le plus petit ensemble de mineurs exclus caractérisant F ; le théorème de Robertson-Seymour affirme que cet ensemble est toujours fini quelle que soit F.

Des exemples d'ensembles d'obstructions finis étaient déjà connus (pour des classes de graphes particuliers) avant que le théorème de Robertson–Seymour soit démontré. Ainsi, la famille des forêts^{[note 8]} a pour seule obstruction le cycle à trois sommets (si l'on se restreint aux graphes simples), c'est-à-dire qu'un graphe est une forêt si et seulement s'il n'a pas ce cycle pour mineur. De même, le théorème de Wagner dit que l'ensemble des obstructions pour les graphes planaires est {K₅, K_3,3}. Un théorème analogue caractérise les graphes planaires extérieurs comme ayant pour obstructions les graphes K₄ et K_2,3.

Le théorème de Robertson-Seymour étend ces résultats à des familles fermées quelconques, mais, étant extrêmement non constructif, ne permet le plus souvent pas, même en principe^{[note 27]}, de déterminer l'ensemble des obstructions d'une famille donnée. Par exemple, l'ensemble des graphes toroïdaux (traçables sur un tore) est une famille fermée dont on ignore l'ensemble des obstructions ; on sait seulement qu'il comporte au moins 17 000 graphes^[22]. En 2020, on ne connait complètement l'ensemble des obstructions pour les familles de graphes traçables sur une surface donnée que dans le cas du plan (les deux graphes mentionnés plus haut) et dans le cas du plan projectif, où cet ensemble comporte 35 graphes^{[23],[note 28]}.

De nombreuses questions d'informatique théorique sont modélisées par des graphes, ou plus précisément par la détermination de propriétés de certains graphes, un exemple célèbre étant le problème du voyageur de commerce.

La démonstration du théorème des mineurs a complètement changé l'estimation qu'on avait de la difficulté algorithmique de certains de ces problèmes. Ainsi, on ignorait jusque-là si la question de savoir si un graphe peut être plongé sans nœuds dans l'espace usuel était calculable, c'est-à-dire décidable par une machine de Turing ; on sait désormais qu'en fait, ce problème appartient à la classe P des problèmes solubles en temps polynomial, bien qu'on ne connaisse toujours aucun algorithme (même très lent) pour le résoudre^[24].

Reconnaissance en temps polynomial

Robertson et Seymour ont démontré que pour tout graphe fixé G, il existe un algorithme en temps polynomial qui teste si un graphe quelconque H possède G comme mineur^[25]. Plus précisément, cet algorithme demande un temps proportionnel au cube du nombre n des sommets et arêtes du graphe testé H (ce que l'on note ${\displaystyle O(n^{3})}$ en notation de Landau). Ce résultat est moins utile en pratique qu'on ne pourrait le croire, parce que la constante de proportionnalité croît avec la taille de G de manière exponentielle. Il en résulte cependant que, pour toute famille fermée F, il existe un algorithme en temps polynomial décidant si un graphe donné G appartient ou non à F : il suffit de contrôler, pour chaque élément de l'ensemble des obstructions de F, s'il est ou non un mineur de G.

L'existence de cet algorithme est donc une conséquence du théorème de Robertson-Seymour, mais ce dernier ne donne aucun moyen effectif de le construire ; il est ainsi possible de démontrer qu'un problème peut être résolu en temps polynomial (dans le langage de la théorie de la complexité, on dit qu'il appartient à la classe P) sans pouvoir exhiber une telle solution : on dit qu'une telle preuve est non constructive^[26]. En revanche, dans de nombreux cas où l'ensemble des obstructions de F est connu explicitement, il est possible de savoir si un graphe appartient à F de manière plus efficace encore ; ainsi, tester si un graphe à n sommets est planaire peut être fait en temps linéaire^[27], c'est-à-dire en temps proportionnel à n.

Pour des invariants de graphes^{[note 25]} ayant la propriété que, pour un k fixé, la famille des graphes d'invariant plus petit que k est fermée^{[note 26]}, le même théorème s'applique ; c'est par exemple le cas de la largeur arborescente, ou du genre minimal de la surface sur laquelle le graphe peut être tracé. Dans chacun de ces cas, pour chaque k fixé, il y a un algorithme permettant, pour un graphe G ayant n sommets et arêtes, de déterminer si son invariant est ou non inférieur à k, en un temps inférieur à ${\displaystyle C(k)n^{3}}$ , où ${\displaystyle C(k)}$ est une constante ne dépendant que de k et de l'invariant mesuré. Un problème ayant cette propriété (où ${\displaystyle n^{3}}$ est remplacé par un polynôme quelconque) est dit soluble à paramètre fixé.

Cependant, cette méthode ne permet pas de construire un algorithme unique permettant de déterminer la valeur d'un tel invariant pour un graphe donné (lorsque cette valeur n'est pas bornée à l'avance), à cause de la difficulté qu'il y a à déterminer l'ensemble des obstructions. De plus, la constante ${\displaystyle C(k)}$ augmente en général extrêmement vite avec k, rendant ces algorithmes très inefficaces en pratique. C'est pourquoi le développement d'algorithmes plus efficaces pour ces problèmes constitue encore en 2020 un important domaine de recherche.

Relation avec le problème P ≟ NP

Le théorème des mineurs semble permettre de construire des algorithmes rapides (polynomiaux, et même cubiques) de résolution de problèmes dont on sait qu'ils sont NP-complets, voire NP-difficiles^[28]. Cependant, une analyse plus précise de la définition de la complexité des algorithmes^{[note 29]} montre que ces algorithmes prennent en fait un temps exponentiel par rapport à la taille des graphes décrivant le problème à résoudre. Ainsi, le problème des chemins disjoints est NP-complet^{[note 30]}, mais Robertson et Seymour ont montré que, à k fixé, le problème des k chemins disjoints est effectivement soluble en temps polynomial^[29] ; cette contradiction apparente^{[note 31]} se résout en remarquant que le temps pris par l'algorithme est un polynôme en n (la taille du graphe étudié) de la forme ${\displaystyle C(k)n^{3}}$ , comme on l'a vu dans la section précédente, mais que la constante ${\displaystyle C(k)}$ augmente au moins exponentiellement avec k, et que c'est elle qui définit la complexité du problème lorsque k est inconnu.

Bien que le théorème de Robertson-Seymour n'ait pas vraiment apporté d'informations nouvelles concernant le problème P ≟ NP, Fellows et Langston ont fait remarquer^[30] que leur démonstration non constructive d'existence d'algorithmes polynomiaux (et où apparaissent souvent, qui plus est, des constantes de proportionnalité bien trop grandes pour qu'ils puissent avoir une utilité pratique quelconque) rend moins claire qu'auparavant la distinction entre algorithmes polynomiaux (considérés comme utilisables de manière réaliste) et non polynomiaux (à jamais inutilisables pour des ensembles de données un peu vastes), et donc que l'intuition de la majorité des informaticiens^{[note 32]}, selon laquelle la classe P est différente de la classe NP, pourrait bien se révéler fausse, sans pour autant que les problèmes NP-complets en deviennent faciles à résoudre.

L'étude de la logique mathématique, c'est-à-dire l'analyse systématique des fondations des mathématiques et des bases logiques sur lesquelles s'appuient les démonstrations, commencée à la fin du dix-neuvième siècle par des logiciens et des mathématiciens tels que Gottlob Frege et Giuseppe Peano, a amené vers 1930 à la découverte de surprenants résultats d'indécidabilité, liés aux célèbres théorèmes d'incomplétude de Gödel ; ces résultats, dont la forme générale est « la théorie T ne permet, pour un certain énoncé E exprimable dans son langage, ni de démontrer E, ni de démontrer sa négation non E », sont souvent dits méta-mathématiques, car ils portent sur les mathématiques elles-mêmes et non sur les objets mathématiques usuels. La plupart des énoncés E ainsi construits étaient généralement jugés artificiels^{[note 33]}, et des énoncés plus conformes à la pratique courante des mathématiciens semblaient ne pas devoir susciter de tels problèmes. Pourtant, vers 1980, Jeff Paris^[31] a obtenu des énoncés de forme apparemment naturelle et inoffensive, par exemple affirmant qu'une certaine suite finit par décroître^{[note 34]}, mais revenant en fait à définir des entiers si grands que leur « existence » ne peut être prouvée à l'aide des seuls axiomes de Peano ; cela implique que, en n'utilisant que ces axiomes, les énoncés en question sont indécidables.

En 1987, Friedman, Robertson et Seymour ont montré que, si le théorème des mineurs était vrai, le théorème suivant (qui en est un cas particulier^{[note 35]}) serait lui aussi, et pour les mêmes raisons, non démontrable dans des systèmes beaucoup plus forts que l'arithmétique de Peano^[32], bien qu'il soit démontrable dans ZFC (et en fait, l'analyse détaillée de la preuve de Robertson et Seymour permet de montrer qu'il est démontrable dans des systèmes nettement moins puissants que ZFC) :

Théorème : Pour tout entier n, il existe un entier m si grand que si G₁, ..., G_m est une suite de graphes finis non orientés, où chaque G_i a au plus n+i sommets et arêtes, alors il existe j < k tels que G_j soit un mineur de G_k.

Là encore, l'entier m est une fonction de n à croissance si rapide^{[note 36]} que les axiomes de Peano (ou même des formes très renforcées de ces axiomes) ne permettent pas de montrer qu'elle est toujours définie, ce qui explique ces résultats d'indécidabilité ; on trouvera dans l'article théorème de Kruskal une description plus précise d'autres théorèmes de logique mathématique analogues, dus eux aussi à Friedman. Ces théorèmes donnent ainsi des exemples de propositions indécidables en arithmétique, considérées comme plus naturelles que celles correspondant au théorème de Gödel^[33].

En 2011, Robertson et Seymour ont achevé la démonstration d'un résultat analogue sur les hypergraphes^[34], définissant un préordre généralisant la relation de mineur, et montrant qu'il s'agit là encore d'un bel ordre. Parmi les conséquences de ce résultat, ils en déduisent que le théorème des mineurs (pour les graphes) s'applique encore si on munit les sommets ou les arêtes d'étiquettes (elles-mêmes ordonnées par un bel ordre), et qu'on demande aux mineurs de respecter l'ordre de ces étiquettes^{[note 37]}. Ce résultat leur a également permis de démontrer une conjecture de Nash-Williams : dans toute suite infinie de graphes, il en existe deux tels que le premier peut être immergé dans le second^{[note 38]}.

Il n'est pas impossible qu'un théorème analogue soit encore vrai pour des graphes infinis dénombrables, mais cette conjecture (ou d'ailleurs sa réfutation) est considérée comme encore plus difficile que ne l'est le théorème des mineurs ; Reinhard Diestel pense qu'elle pourrait être liée à une autre conjecture de Seymour, affirmant que tout graphe infini dénombrable possède un mineur (strictement plus petit) qui lui est isomorphe^[35]. En revanche, on sait que ces résultats sont faux pour des graphes non dénombrables : Péter Komjáth (en) a démontré que, si ${\displaystyle \lambda }$ est un cardinal non dénombrable, il existe ${\displaystyle 2^{\lambda }}$ graphes de cardinal ${\displaystyle \lambda }$ dont aucun n'est un mineur d'un autre^[36], et Bogdan Oporowski a obtenu un contre-exemple à la conjecture de Seymour dans le cas non dénombrable^[37].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Robertson–Seymour theorem » (voir la liste des auteurs).

Notes