Soutenance de Samuel HUMEAU sous la direction de Damien POUS.
Résumé de la thèse
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.
A tree decomposition allows one to understand a graph as a tree via the identification of some vertices. By minimising the maximal number of vertices identified as a single vertex in such decompositions, we obtain the treewidth of the graph: this is a graph parameter somehow expressing how close a graph is to being a tree.
Treewidth has multiple origins as well as many applications. There are several equivalent definition of this parameter: a graph has treewidth at most k iff it avoids a certain finite list of graphs as minors, or iff it can be reduced to the empty graph via a certain graph rewriting system. The issue with these definitions is that the exact lists of minors or rewriting systems are not known explicitly whenever k is as big as 4 or 5, respectively.
Another characterisation of treewidth is the following: the graphs of treewidth at most k are generated by an inductive finite syntax whose operations are interpreted on graphs. This is a natural generalisation of the usual inductive characterisation of trees: an isolated vertex is a tree of which it is its root, a tree is a root adjacent to the roots of its subtrees. This syntax imposes a notion of rootedness. For treewidth, istead of a unique root, a graph has up to k+1 roots at a given time, called its sources and used as interface in graph operations.
A question asked by Courcelle and Engelfriet is the following: is there a finite equational theory corresponding to the isomorphism of graphs of treewidth at most k? Said otherwise, is there a finite list of equations on the syntax of graphs of treewidth at most k so that two terms from the syntax are provably equal via the axioms iff their graphs are isomorphic ? Pous and Cosme-Llopez have solved the case k=2 positively. The first part of this thesis has been focused on finding a positive proof for the case k=3.
For this proof, we use a syntax generalising series-parallel expressions, denoting graphs with a small interface. We introduce appropriate notions of connectivity for graph of bounded treewidth (corresponding to components, cutvertices, and 2-separators, respectively). We use those concepts to analyse the structure of graphs of treewidth at most 3, showing how they can be decomposed recursively, first canonically into connected parallel components, and then non-deterministically. The main difficulty consists in showing that all non-deterministic choices can be related using only finitely many equational axioms.
This proof relies on a specific lemma expressing which constraints apply on graphs avoiding the triangle as a minor. To generalise the proof to k=4, this lemma should be generalised to understand graphs avoiding the tetrahedron as a minor. Such a result already exists. Its proof relies on the two-paths theorem.
A tuple (s,t,u,v) of vertices in a simple undirected graph is 2-linked when there are two vertex-disjoint paths respectively from s to t and from u to v. A graph is 2-linked when all such tuples are 2-linked.
The second part of this thesis is a new and simple proof of the two-paths theorem, a characterisation of edge-maximal graphs which are not 2-linked as webs: particular near triangulations of the plane filled with cliques. Our proof works by generalising the theorem, replacing the four vertices above by an arbitrary tuple; it does not require major theorems such as Kuratowski's or Menger's theorems. Instead it follows an inductive characterisation of generalised webs via parallel composition, a graph operation consisting in taking a disjoint union before identifying some pairs of vertices. This operation is also used in the operational characterisations of graphs of bounded treewidth discussed above.
We use the insights provided by this proof to design a simple O(nm) recursive algorithm for the ``two vertex-disjoint paths'' problem. This algorithm is constructive in that it returns either two disjoint paths, or an embedding of the input graph into a web.
Gratuit
Disciplines