Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Ma thèse de Doctorat est basée sur un sujet très intéressant en Théorie de Graphe : Le tournoi.En 1934, Rédei a prouvé que tout tournoi contient un chemin Hamiltonien direct. En 1971, Grünbaum a prouvé que tout tournoi contient tout chemin Hamiltonien antidirect avec exactement trois exceptions. Un circuit d'ordre trois, un tournoi régulier d'ordre cinq et un tournoi de Paley d'ordre sept ne contiennent pas un chemin Hamiltonien antidirect. En 1972, Rosenfeld, inspiré par le résultat de Grünbaum, propose la conjecture suivante: Conjecture de Rosenfeld: il existe k≥ 8 tel que tout tournoi d'ordre n ≥ K contient tout chemin Hamiltonien orienté.Alspach, Rosenfeld et Straight ont prouvé la conjecture de Rosenfeld pour les chemins à deux blocs.En 1973, Forcade a prouvé la conjecture de Rosenfeld dans le cas de tournois d'ordre 2^n. Thomason était le premier à donner une réponse générale. Il a proposé, en 1986, qu'il existe n_0≤2^128, tel que, pour tout entier n ≥ no, tout tournoi d'ordre n contient tout chemin Hamiltonien orienté. Il a encore démontré que tout ensemble de b_1+1 sommets dans un n-tournoi contient un origine de tout (n-1)-chemin ayant son premier bloc de longueur b_1.En 2000, Havet et Thomassé avaient amélioré cette idée-clé introduite par Thomasonet avaient démontré que tout tournoi T d'ordre n contient tout chemin P d'ordre n avec exactement les exceptions de Grünbaum. Pour tout z et y, deux sommets de T, ils ont defini s^+ (x,y) =|{z ∈V(T)┤ tel que z peut être atteint par un chemin direct d'origine x ou y} et ils ont prouvé que si s^+ (x,y) ≥ b_1+1, alors x ou y est un origine d'un tel chemin. Cette nouvelle idée-clé leur permet de remarquer que la démonstration de l'existence d'un n-1-chemin orienté dans un n-tournoi est équivalente à l'existence de tout chemin Hamiltonien P dans ce tournoi sauf si (T. P) est l'un parmi 69 exceptions qui étaient vérifiées l'une après l'autre. Leur preuve était longue et compliquée. Encouragé par la confiance de mon Professeur Amine El Sahili de l'existence d'une ...