Chemins, cycles et arbres dans les tournois.

Thèse présentée devant l'Université Claude Bernard Lyon 1
pour l'obtention du diplôme de doctorat

Frédéric Havet

 


Version postcript


Cette thèse a été effectuée sous la direction de J. A. Bondy.
La soutenance a eu lieu le 12 Janvier 1999 à l'université Claude Bernard de Lyon I.

 Rapporteurs:
P. HELL, Full Professor, Simon Fraser University, Canada
M. LAS-VERGNAS, Directeur de Recherche, Equipe Combinatoire, Paris VI
A. G. THOMASON, Lecturer, University of Cambridge, Grande-Bretagne
 Jury:
J. A. BONDY, Professeur, Université Claude Bernard Lyon I
P. CAMION, Directeur de Recherche Emerite, I.N.R.I.A. Rocquencourt (président)
A. GOLDMAN, Professeur, Université Claude Bernard Lyon I
M. LAS-VERGNAS, Directeur de Recherche, Equipe Combinatoire, Paris VI
J. ZENG, Professeur, Université Claude Bernard Lyon I



 RESUME:

Chapitre 1  Introduction.

Il existe de nombreux rapports entre les orientations et les colorations d'un graphe. Le plus ancien est le théorème de Gallai-Roy qui affirme que toute orientation d'un graphe k-chromatique contient un chemin direct (toutes les arêtes dans le même sens) d'ordre k. Plus généralement, on peut se demander quels sont les graphes orientés qui sont contenus dans toutes les orientations d'un graphe k-chromatique. Pour aborder ce problème, il est naturel de chercher d'abord les graphes orientés qui sont contenus dans les orientations des graphes complets, c'est à dire les tournois. En effet, le graphe complet à k éléments est le graphe k-chromatique le plus simple. Dans cette thèse nous nous intéressons à l'existence de chemins, cycles et arbres dans les tournois et dans le dernier chapitre, nous considérons le côté algorithmique du problème.



Chapitre 2  Chemins dans les tournois.

Un des premiers résultats sur les tournois affirme l'existence d'un chemin hamiltonien direct dans tout tournoi. Plutôt que de regarder les chemins directs, on peut s'intéresser à l'existence de chemins orientés quelconques dans un tournoi. En 1971, Grünbaum prouva que tout tournoi contient les chemins hamiltoniens alternés (deux arêtes consécutives sont de sens opposé), à part trois exceptions: le 3-cycle, le tournoi régulier à 5 sommets et le tournoi de Paley à 7 sommets. En 1972, Rosenfeld conjectura qu'il existe un entier N>7 tel que tout tournoi d'ordre n>=N contient tout chemin orienté hamiltonien. Cette conjecture a été vérifiée pour les chemins à deux blocs par Alspach et Rosenfeld et pour tous les chemins si n=2k par Forcade. Enfin, Thomason l'a prouvée pour les tournois d'ordre n>=2128 et a conjecturé qu'elle était vraie pour n>7.

Avec Stephan Thomassé, nous avons complètement établi la conjecture de Rosenfeld en prouvant le théorème suivant:


Théorème 1   Soient T un tournoi d'ordre n et P un chemin d'ordre k<= n. Alors T contient P si et seulement si (T;P) n'est pas une exception de Grünbaum.




Chapitre 3  Cycles dans les tournois.

La suite logique de ce travail est l'étude de l'existence de cycles dans un tournoi. Elle démarre là aussi sur un résultat classique: Un tournoi contient un cycle hamiltonien direct si et seulement si il est fortement connexe. On peut là aussi se pencher sur l'existence de cycles hamiltoniens quelconques dans un tournoi. En 1974, Rosenfeld conjectura qu'il existe un entier N tel que tout tournoi d'ordre n>= N contient tout cycle hamiltonien non direct. Elle a été vérifiée pour les cycles avec un bloc de taille n-1 par Grünbaum, pour les cycles alternés par Thomassen (n>= 50), Rosenfeld (n>= 28) et Petrovic (n>= 16), et pour les cycles ayant deux blocs par Benhocine et Wojda. Thomason l'a prouvée pour n>= 2128 et a conjecturé qu'elle était vraie pour n>= 9.

Nous établissons plusieurs résultats partiels.

Théorème 2   Soit T un tournoi réductible d'ordre n et C un cycle orienténon direct d'ordre n. Alors T contient C.

Théorème 3   Soit T un tournoi k-fortement connexe (k>= 1) d'ordre n>= 6 et C un cycle d'ordre n qui contient un bloc de longueur au moins k+3. Alors T contient C.

Théorème 4   Si T est un tournoi 1-fortement connexe d'ordre n>= 9 et C un cycle d'ordre n alors T contient C.


De plus, pour chacun de ces résultats, nous caractérisons toutes les exceptions de petits ordres.



Chapitre 4  Arbres dans les tournois.

Soit f(n) le plus petit entier tel que tout tournoi d'ordre f(n) contient tout arbre orienté d'ordre n. Et soit g(k) le plus petit entier tel que tout tournoi d'ordre n+g(k) contient tout arbre orienté d'ordre n ayant k feuilles. Sumner a conjecturé que f(n) = 2n - 2 en remarquant que cette condition est nécessaire. En effet, un tournoi régulier à 2n-1 sommets ne contient pas de sommets de degré externe n-1 ou plus et ne contient donc pas l'arbre orienté composé d'une racine dominant n-1 feuilles. Häggkvist et Thomason ont prouvé f(n)<= 12n et f(n)<= (4+o(1))n. De plus, ils ont prouvé que g(k)<= 2512k3.

Avec Stéphan Thomassé, nous conjecturons que g(k)<= k-1. Cette conjecture implique celle de Sumner.

Nous montrons que g(3)<= 5. Nous en déduisons que f(n)<= 38/ 5 n.



Chapitre 5  Algorithmie.

Dans ce chapitre, nous exposons des algorithmes rapides correspondant aux preuves des chapitres 1 et 2: nous donnons des algorithmes en O(n2) pour trouver un chemin hamiltonien dans un tournoi, un cyle hamiltonien non-direct dans un tournoi réductible ou 1-fortement connexe et un cycle ayant un bloc de taille au moins k+2 dans un tournoi k-fortement connexe.



havet@jonas.univ-lyon1.fr