Structures and equations of sourced graphs : small treewidth and disjoint paths

Une décomposition arborescente permet de comprendre un graphe quelconque comme un arbre, au prix de l'identification de certains sommets. En minimisant le nombre maximal de sommets identifiés entre eux, on obtient la largeur arborescente d'un graphe. Il s'agit là d'un paramètre de graphe exprimant la proximité d'un graphe à une structure d'arbre. La largeur arborescente a de multiples origines et de nombreuses applications. Parmi ces différentes caractérisations on peut compter celle par les mineurs exclus minimaux, et celle par des systèmes de réécriture de graphes. Une des particularités de ces caractérisations est que les mineurs et systèmes de réécriture exacts ne sont pas connus dès que la largeur arborescente dépasse 4 ou 5, respectivement. Une autre caractérisation est la suivante: les graphes de largeur arborescente au plus k sont générés par une syntaxe inductive finie dont les opérations sont interprétées sur les graphes. C'est une généralisation naturelle de la définition inductive des arbres: un sommet isolé est un arbre dont il est la racine, un arbre est une racine adjacente aux racines de ses sous-arbres. Cette syntaxe force une notion d'enracinement. Pour la largeur arborescente, en place d'une racine unique, un graphe peut avoir jusqu'à k+1 racines, appelées sources et servant d'interface pour les opérations de graphes.Un problème posé par Courcelle et Engelfriet est le suivant: existe-t-il une théorie équationnelle finie correspondant à l'isomorphisme des graphes de largeurs arborescente bornée ? Autrement dit, existe-t-il une liste finie d'axiomes équationnels sur la syntaxe des graphes de largeur au plus k de sorte que deux termes associés soit prouvablement égaux si, et seulement si, leur graphes sont isomorphes ? Pous et Cosme-Llopez ont résolu le cas k=2 par la positive. La première partie de cette thèse donne une réponse positive au cas k=3.On utilise alors une syntaxe généralisant celle des graphes série-parallèles. On introduit des notions de connectivité pour les graphes de largeur bornée (correspondant au composantes connexes, points d'articulation et 2-séparateurs, respectivement). On utilise ces outils pour analyser la structure des graphes de largeur au plus 3, montrant comment ceux-ci peuvent se décomposer récursivement, d'une manière d'abord canonique puis non-déterministe. La difficulté réside dans la preuve que tous les choix non-déterministes sont équivalents par les axiomes. Notre preuve utilise un lemme décrivant la forme des graphes n'ayant pas de triangle comme mineur sourcé. Pour la généraliser à k=4, il faudrait un résultat similaire pour les graphes ne contenant pas de tétrahèdre comme mineur sourcé. Un tel résultat existe et sa preuve utilise le théorème des deux chemins. Dans un graphe, un quadruplet (s,t,u,v) de sommets est 2-lié quand il existe deux chemins disjoints, l'un allant de s à t, et l'autre de u à v. Un graphe est dit 2-lié quand tout quadruplet de sommets est 2-lié.La deuxième partie de cette thèse donne une nouvelle preuve simple du théorème des deux chemins. Ce dernier est une caractérisation par les toiles des graphes maximaux (vis-à-vis des arrêtes) n'étant pas 2-liés. Les toiles sont des graphes semblables à des triangulations du plans remplies de graphes complets. Notre preuve généralise ce théorème, remplaçant les quadruplets par des tuples quelconques. Elle n'utilise ni le théorème de Menger, ni celui de Kuratowski. À la place, elle suit une définition inductive des toiles par des compositions parallèles. Cette opération est aussi l'une de celles générant les graphes de largeur bornée. De notre preuve du théorème des deux chemins nous déduisons un algorithme récursif simple pour le problème des chemins disjoints. Cet algorithme est constructif en ce qu'il renvoie soit deux chemins disjoints, soit un plongement du graphe en entrée dans une toile.