Problèmes de connexité en théorie de graphes : structures, algorithmes et complexité ; Connectivity problems in graph theory : structures, algorithms and complexity
You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Text;
Electronic Thesis;
E-Book
Title:
Problèmes de connexité en théorie de graphes : structures, algorithmes et complexité ; Connectivity problems in graph theory : structures, algorithms and complexity
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Cette thèse traite 3 classes de problèmes liés à la connexité des graphes. En premier lieu, nous traitons des orientations des graphes où une orientation d’un graphe non-orienté est obtenue en remplaçant chaque arête par un arc entre les mêmes deux sommets. Ce chapitre est divisé en deux parties : l’une sur les orientations pour l’arête-connexité et l’autre sur les orientations pour la sommet-connexité. Pour l’arête-connexité, nous présentons certains résultats liés au théorème fort de Nash-Williams sur les orientations et nous démontrons qu’il est co-NP-complet de décider si un odd-vertex pairing donné est admissible. Ceci répond à une question posée par Frank. Ensuite, nous prouvons qu’il est NP-complet de décider si un graphe a une orientation satisfaisante des conditions d’arc-connexité locale arbitraires données et nous mentionnons quelques problèmes liés. Ensuite, nous présentons certains résultats partiels sur le problème de décider si un graphe donné a une orientation fortement connexe telle que le degré entrant de chaque sommet a une certaine parité assignée. Finalement, nous souhaitons traiter une propriété de connexité des orientations des graphes 3-arête-connexes qui se situe entre la connexité forte et la 2-arc-connexité. Ce problème a été proposé par Frank et mène à l’introduction d’un nouvel invariant des graphes 3-arête-connexes. Nous démontrons plusieurs bornes pour cet invariant.Pour le sommet-connexité, nous présentons d’abord une collection de résultats antérieurs.Puis, nous traitons un problème proposé par Cheriyan, déterminant quelques classes restreintes de graphes eulériens tel que chacune de leurs orientations eulériennes a une grande sommet-connexité.Le chapitre suivant porte sur les packages d’arborescences. D’abord, nous proposons une méthode récursive qui permet de déduire des théorèmes sur les packages d’arborescences d’accessibilité à partir des théorèmes sur les packages d’arborescences couvrantes dans plusieurs contextes. En particulier, nous déduisons un théorème de Kamiyama, ...