Exploration des graphes aretes-colorees

Dans la pratique, énormément de problèmes concrets peuvent être modélisés par un graphe. Par exemple, une carte géographique est typiquement un graphe dans lequel on serait amener à chercher des chemins courts entre les villes, ou à passer par toutes les routes ou toutes les villes…etc. Cela explique pourquoi la théorie des graphes est certainement le domaine le plus populaire des mathématiques discrètes malgré son jeune âge. En général, cette théorie est partitionnée en deux branches : la branche des graphes non-orientés et la branche des graphes orientés. Pendant longtemps, les graphes nonorientés ont été les plus étudiés. Pourtant, ils peuvent être considérés comme une sousclasse des graphes orientés puisqu’une arête peut être représentée par deux arcs opposés. Mais, l’importance théorique et pratique des graphes orientés s’est imposée dans les vingt dernières années. Et on parle maintenant de plus de trois mille publications concernant les graphes orientés. Malheureusement, les problèmes pratiques ne cessent de devenir de plus en plus compliqués et leurs représentations de plus en plus difficiles à satisfaire par certains graphes. D’où l’importance d’ajouter de nouveaux concepts dans leurs définitions pour augmenter leur représentativité de la réalité. Dans cette thèse, nous traitons les graphes c-arêtescolorées qui sont une généralisation des graphes orientés. Un graphe c-arêtes-colorées est un graphe non-orienté dont les arêtes sont colorées par un nombre donné de couleurs c inférieur ou égal au nombre des arêtes bien sûr. Cette définition engendre énormément de nouvelles questions plus toutes les questions qu’on pourrait poser dans le cas des graphes classiques.

Les graphes arêtes-colorées trouvent beaucoup de champ d’application notamment en biologie moléculaire pour modéliser les séquences d’ADN. Le livre de Pevzner [P00] y consacre un chapitre et propose une série de problèmes ouverts. A titre d’exemple aussi, dans [A89], l’auteur ramène le problème de la recherche d’un carré latin à un problème de cycle hamiltonien alterné dans un graphe complet arêtes-colorées. Les carrés latins sont des matrices carrés qui vérifient certaines propriétés mathématiques et qui sont utilisées surtout dans la modélisation en statistique appliquée et les plans d’expériences. En théorie, parmi les choses qu’on pourait citer, les tournois bipartis qui sont intimement liés aux graphes complets 2-arêtes-coloriées. R. Häggkvist et Y. Manoussakis [HM89] ont montré que tout tournoi biparti peut être considéré comme un graphe complet 2 arêtes-coloriées.

Graphes arêtes-colorées

Terminologie

Soit Ic = {1, 2, ··· , c} un ensemble donné de couleurs, c ≥ 2. Gc dénote un graphe arêtes-colorées simple tel que chaque arête est colorée par une couleur i ∈ Ic sans que deux arêtes parallèles joignent la même paire de sommets. S’il s’agit d’un graphe simple non arêtes-colorées nous le noterons simplement G. S’il s’agit d’un multigraphe arêtescolorées, c.à.d. qui admet des arêtes parallèles joignant deux sommets, nous le noterons Gc . Pour les graphes complets arêtes-colorés, on écrit Kc n à la place de Gc . S’il s’agit d’un multigraphe complet arêtes-colorées on écrit Kc n. Si un graphe biparti arêtes-colorées est simple on écrit Bc , s’il est multigraphe on ecrit Bc . Si un graphe biparti complet arêtescolorées est simple on écrit Kc n,n, s’il est multigraphe on écrit Kc n,n. Pour simplifier et sans perdre de généralité, nous définissons les notions seulement pour le cas des graphes Gc .

Les deux ensembles des sommets et des arêtes de Gc sont notés V (Gc) et E(Gc), respectivement. L’ordre de Gc est le nombre de ses sommets, noté n. La taille de Gc est le nombre de ses arêtes, noté m. Pour une couleur donnée i, Ei (Gc ) dénote l’ensemble des arêtes de Gc dont la couleur est i.

Une arête incidente à x et y est notée xy, sa couleur est c(xy) et son coût (si elle a un coût) est cout ˆ (xy). Le coût d’un sous-graphe est la somme des coûts de ses arêtes. Un sousgraphe de Gc contenant au moins deux arêtes est dit proprement arêtes-colorées, si chaque deux arêtes adjacentes dans ce sous-graphe ont deux couleurs différentes. Une chaîne proprement-arêtes-colorées n’admet pas de répétition de sommets et chaque deux arêtes successives, dans cette chaîne, ont deux couleurs différentes. Une marche proprementarêtes-colorées n’admet pas de répétition d’arêtes et chaque deux arêtes successives, dans cette marche, ont deux couleurs différentes. La longueur d’une chaîne (resp. marche) est le nombre de ses arêtes. Soient deux sommets s et t dans Gc , on définit (si elle existe) une s − t chaîne (resp. marche) telle qu’une chaîne (resp. marche) d’extrémités s et t. Parfois, s sera appelé la source et t la destination de la chaîne (resp. marche). De même, notons (x, y) chaîne (resp. marche) d’extrémités s et t, une s−t chaîne (resp. marche) de longueur x+y telle que les x premières arêtes ont une couleur et les y arêtes suivantes ont une autre couleur. Un (x, y) cycle est un cycle de longueur x + y telle que les x premières arêtes ont une couleur et les y arêtes suivantes ont une autre couleur. Une chaîne/marche proprement-arêtes-colorées est dite fermée si ses extrémités coïncident et sa première et sa dernière arête ont deux couleurs différentes. Une chaîne fermée proprement-arêtescolorées est appelée un cycle proprement-arêtes-colorées. Une marche est dite eulérienne si elle passe par toutes les arêtes du graphe. On dit qu’une chaîne est hamiltonienne si elle passe par tous les sommets. De même on dit qu’un cycle est hamiltonien s’il passe par tous les sommets.

Aussi, pour un sous-graphe donné Q induit par un graphe G non arêtes-colorées, une contraction de Q dans G consiste à remplacer Q par un nouveau sommet, soit zQ, tel que chaque sommet x dans G−Q est connecté à zQ par une arête si, et seulement si, il existe une arête xy dans G pour un certain sommet y dans Q.

Définitions

Définition 1.1 (coupe-sommet, coupe-arête) Dans un graphe connexe, un coupe-sommet (resp. une coupe-arête) est un sommet (resp.une arête) que si on l’enlève, alors le graphe ne sera plus connexe.

Définition 1.2 (sommet séparateur de couleurs) Dans un graphe Gc , x est un sommet séparateur de couleurs si, et seulement si, x est un coupe sommet monochromatique par rapport à chacun des sous-graphes connexes Gc qu’on peut obtenir par enlèvement de x.

Définition 1.3 (arête séparatrice de couleurs) Dans un graphe Gc , e est une arête séparatrice de couleurs si, et seulement si, e est une coupe-arête dont les deux extrémités sont des sommets monochromatiques par rapport à chacun des sous graphes connexes de Gc qu’on peut obtenir par enlèvement de e.

Définition 1.4 (compatibilité avec un couplage) Un cycle (resp. une chaîne) dans un graphe Gc est compatible avec un couplage M si, et seulement si, les arêtes de ce cycle (resp. cette chaîne) sont pris alternativement de M et de Gc − M.

Les facteurs proprement-arêtes-colorées sont intimement liés aux cycles hamiltoniens en voici la définition :

Définition 1.5 (facteur proprement-arêtes-colorées) Un facteur F est un ensemble de cycles sommets-disjoints qui couvrent tous les sommets du graphe. On dit que le facteur F est proprement-arêtes-colorées si, et seulement si, tous les cycles qui le constituent le sont aussi (quand il s’agit de deux couleurs on parle d’un facteur alterné).

Définition 1.6 (un graphe s-régulier) Soit s ≥ 0, un graphe s-régulier est un graphe dont tous les sommets ont un degré égal à s.

Remarque 1 Un facteur est un graphe 2-régulier.

S’il n’existe pas un facteur proprement-arêtes-colorées, il reste toujours une chance d’avoir des structures proprement-arêtes-colorées, qui couvrent tout le graphe, formées de chaînes et de cycles. En particulier s’ils existent de m chaînes-cycles-proprement-arêtescolorées.

Définition 1.7 (m-chaînes-cycles-proprement-arêtes-colorées) Soient m ≥ 0 et Gc , un m-chaînes-cycles-proprement-arêtes-colorées est un sous-graphe de Gc constitué de m chaînes proprement-arêtes-colorées et un certain nombre de cycles proprement-arêtes-colorées tous sommets-disjoints. Un sous-graphe 0 chaînes-cycles-proprementarêtes-colorées (m = 0) n’est autre qu’un facteur proprement-arêtes-colorées.

Remarque 2 Un sous-graphe 1-chaînes-cycles-proprement-arêtes-colorées est appelé aussi un presque-facteur proprement-arêtes-colorées.

Soient X et Y deux sous-ensembles de V (Gc ), alors XY désigne l’ensemble des arêtes entre les sommets de X et Y . Si toutes les arêtes de XY ont la même couleur, cette couleur sera noté c(XY ). Soit C un cycle alterné de longueur 2p, p ≥ 2, parfois il est pratique de diviser les sommets de C en deux ensembles X = {x1, x2,…,xp} et Y = {y1, y2,…,yp} tel que C = x1y1x2y2 …xpyp et c(xiyi) = c(yixi+1) pour i = 1, 2,…,p.

Définition 1.8 (dominance entre cycles alternés) On dit qu’un cycle alerné C1 domine un autre cycle alterné C2 et on note (C1 ⇒ C2) si, et seulement si, c(X1C2) ≠ c(Y1C2). On note C1 ⇎ C2 le fait que ni C1 ⇒ C2 ni C1 ⇒ C2.

Table des matières

Introduction
I Généralités & État des lieux
1 Généralités et notions préliminaires
1.1 Graphes arêtes-colorées
1.1.1 Terminologie
1.1.2 Définitions
1.2 Théorie de la complexité
1.2.1 Optimisation combinatoire
1.2.2 Classes d’approximation
1.2.3 Inapproximation
1.3 Conclusion
2 État de l’art
2.1 Cycles hamiltoniens proprement-arêtes-colorées
2.2 Chaînes hamiltoniennes proprement-arêtes-colorées
2.3 Connexité : couleur-connexité et cyclique-connexité
2.3.1 s − t chaînes proprement-arêtes-colorées
2.3.2 Cycles non hamiltoniens proprement-arêtes-colorées
2.4 (x, y) chaînes/cycles
2.5 Marches eulériennes proprement-arêtes-colorées
2.6 Sous-graphes hétérochromatiques
2.6.1 Arbres hétérochromatiques
2.6.2 Chaînes/cycles hétérochromatiques
2.7 N P-complétude
2.8 Conclusion
II Contributions
3 Facteurs, Cycles et Chaînes proprement-arêtes-colorées
3.1 Facteur proprement-arêtes-colorées
3.2 Le i-degré minimum dans les graphes (simples) arêtes-colorées
3.2.1 Le i-degré minimum supérieur ou égal à 1
3.3 Le i-degré minimum dans les multigraphes arêtes-colorées
3.3.1 Le i-degré minimum supérieur ou égal à 1
3.3.2 Le i-degré minimum très grand
3.4 Graphe aléatoire
3.5 Conclusion
4 Arbres couvrants arêtes-colorées
4.1 Arbres couvrants proprement-arêtes-colorées
4.1.1 1-arbre-cycle-proprement-arêtes-colorées
4.1.2 N P-complétude
4.1.3 Inapproximation
4.2 Arbres couvrants faiblement-arêtes-colorées
4.2.1 N P-complétude
4.2.2 Inapproximation
4.3 Conclusion
5 s-t chaînes/marches proprement-arêtes-colorées
5.0.1 Une s − t marche proprement-arêtes-colorées
5.1 La plus courte chaîne/marche proprement-arêtes-colorées
5.2 La plus longue s − t chaîne/marche proprement-arêtes-colorées
5.3 Les paires de sommets interdits dans une s − t chaîne
5.4 Conclusion
6 k-chaînes/marches proprement-arêtes-colorées
6.1 N P-complétude dans des graphes quelconques
6.2 N P-complétude dans les graphes sans cycles ni marches fermées tous proprement-arêtes-colorées
6.3 Quelques approximations et résultats polynomiaux
6.4 Conclusion
Conclusion
Perspectives

Lire le rapport complet