Graphes arbitrairement partitionnables : propriétés structurelles et algorithmiques
Institution:
Versailles-St Quentin en YvelinesDisciplines:
Directors:
Abstract EN:
Graphes decomposition problems are in the heart of graphes theory. In this thesis we study the problem Graph_Partition wich in defined as follow. Being done a n-vertex graph ans a partition of n (a sequence of positives integers whose sum is equal to n), does it exists a partition of the vertex set such that every set of the partition induce a connected sub-graph, and the sequence of vertices numbers of these sub-graphes is a permutation of the partition of n. If a such partition of the vertex set exists, we say that the graph is decomposable for this partition of n. The problem Graph_Partition has already been the target of several studies. It has been shown that this problem is NP-Complet even restreint to the set of trees, and arbitrarily decomposable trees are principaly of degree 3. In this thesis we have in a first time continued structural study on arbitrarily decomposable and we have started structural studies on arbitrarily decomposable graphs. We have shown that arbitrarily decomposable trees with length arbitrarily haigh are exactly the set of combs. We gave an introduction building wich allow to construct arbitrarily decomposable combs with a number of degree 3 vertices and a length arbitrarily high. We have also given a first contribution concerning structural study of arbitrarily decomposable minimal graphs (whatever the edge you remove from the graph, the remaining graph is not arbitrarily decomposable). In a second time we study algorithmic aspect. We have shown that if we consider partition of n containing few integers, it is possible to determine enough quickly if a graph in decomposable for this partition of n. We have extended this result over the graphs containing few degree 3 vertices. Finally we have shown that it is possible to decide enough quickly if a tree with large diameter in arbitrarily decomposable.
Abstract FR:
Les problèmes de décomposition de graphes sont au coeur de la théorie des graphes. Dans cette thèse nous étudions le problème Graphe_Partition qui, étant donné un graphe d'ordre n et une partition de n (séquence d'entiers positifs dont la somme est égale à n), consiste à déterminer s'il existe une partition des sommets du graphe telle que chaque ensemble de cette partition induit un sous-graphe connexe et la séquence des ordres de ces sous-graphes est une permutation de la partition de n. Si une telle partition des sommets existe, nous dirons que le graphe est décomposable pour cette partition de n. Un graphe arbitrairement décomposable est un graphe décomposable pour toutes les partitions de n. Le problème_Partition a déjà été l'objet de plusieurs études. Il a notamment été montré que celui-ci est NP-complet même restreint à la classe des arbres et que les arbres arbitrairement décomposables sont principalement de degré inférieur ou égale à 3. Dans cette thèsenous avons dans un premier temps approfondie l'étude structurelle des arbres arbitrairement décomposables et commencé l'étude structurelle des graphes décomposables. Nous avons pu montrer que les graphes décomposables de longueur arbitrairement grande étaient exactement l'ensemble des peignes. Nous avons donné une construction par récurrence qui permet de construire des peignes arbitrairement décomposables contenant un nombre de sommets de degré 3 et de longueurs arbitrairement grands. Nous avons apporté également une première contribution concernant l'étude structurelle des graphes arbitrairement décomposables minimaux (quelle que soit l'arrête que l'on retire, le graphe restant n'est plus décomposable). Puis dans un deuxième temps, nous nous sommes intéressés à l'aspect algorithmique. Nous avons notamment montré que pour des partitions de n contenant peu d'entiers, il était possible de déterminer assez rapidement si un graphe était décomposable pour cette partition. Nous avons étendu ce résultat aux graphes contenant un petit nombre de sommets de degré 3. Enfin, nous avons montré qu'il était possible de déterminer assez rapidement si un arbre de large diamètre est arbitrairement décomposable.