Télécharger le fichier original (Mémoire de fin d’études)
Majoration
Théorème 6 Soit G = (S , A) un graphe d’ordre n de nombre chromatique γ(G) et de degré de stabilité α(G), alors on a :
γ(G) + α(G) ≤ n + 1 Preuve Considérons S un stable maximum de G. Une coloration possible des sommets consiste à colorier les sommets de S d’une même couleur et les ( n – α(G) ) autres sommets de couleurs toutes différentes d’où : γ(G) ≤ 1 + (n – α(G) ) γ(G) + α(G) ≤ 1 + n Théorème 7 (Gaddum, Northaus, 1960) Soit G, le graphe complémentaire du graphe G, alors on a γ(G) ≤ n + 1 – γ (G) Preuve Le graphe complémentaire de G = (S , A) est défini par G = (S , A) Ou A est le complémentaire de A
l’inégalité est vérifiée pour n = 1 et n = 2
Supposons la vérifiée pour tout graphe de n-1 sommets et considérons un graphe G de n sommets, ou n > 2 ; désignons par Gs0 le sous graphe obtenu par suppression d’un somme s0
Gs0= G – s0 On a assurément γ(G) ≤ γ(Gs0) + 1 (1) + 1 (2) γ(G) ≤ γ (Gs0)
(1) + (2) donne γ(G) + γ(G) ≤ γ(Gs0) + γ (Gs0) + 1 et en vertu de l’hypothèse d’induction γ (G) + γ ( G) ≤ (n-1) +1+1 = n+1, d’ou le résultat.
Corollaire 4 Soit le graphe complémentaire du graphe G = (S , A) d’ordre n, G = (S,A) alors on a n+1 ² 1 γ(G) ≤ . . 2 γ(G)
Preuve En effet on 4 γ (G) γ ≤(γ(G))-γ +4γ(G) γ (G) (G))² (G) 4γ(G) γ ( G) ≤ (γ (G) +γ (G) )² ≤ (n+1)² d’après le théorème 2 d’où n+1 ² 1 γ(G) ≤ . 2 γ(G)
Théorème 8 (WELSH 1960) Si dans un graphe G = (S , A), une partition (S1, S2,…, Sq ) est une q- coloration (non nécessairement minimum), et si l’on pose d k = max dG (x) alors on a x Є S k γ(G) ≤ max min [k, d k + 1] k ≤ q
Preuve. 1) Si S1 n’est pas stable maximal, ajoutons-lui des sommets jusqu’à obtenir un ensemble S’ 1 stable maximal, Si S2 – S’1 n’est pas stable maximal dans S – S’ 1 , on le complète de même pour obtenir un S’2 stable maximal dans S – S’1 , etc… De cette façon on définit une nouvelle coloration (S’1, S’2, …S’r) avec r ≤ q et min (k , r) avec U S’i כ SK (k = 1, 2, …, q)
i = 1
2) Désignons par i (x) l’indice i tel que x Є S’i. Soit x un sommet avec i (x) = k, comme x est adjacent à tout S’j , avec j ≤ k-1 (en vertu de la maximalité de S’j), on a : dG (x) ≥ k – 1 d’ou i (x) dG (x) + 1
3) Soit x o un sommet de SK ; on a i (x o) ≤ k, en vertu de (1), et par conséquent i (x o) ≤ max i (x) ≤ max (dG (x) + 1) = d k + 1 x Є S k x Є S k d’ou finalement
γ(G) ≤ max i (xo) ≤ max min {k; d K + 1} xo k ≤ q
Corollaire 5 Soit G un graphe dont les sommets sont indexés de sorte que dG (x1) ≥ dG (x2) ≥ …≥ dG (s n)
Si pour un entier q ≥ o, le nombre de sommets de degré ≥ q + 1 est ≤ q + 1 (et en particulier, pour q ≤ n-2, si dG (x q + 2) ≤ q), alors on a : γ(G) ≤ q + 1
Preuve En effet, considérons la n-coloration ({x l}, {x 2},….{x 4},….. {x n}) On a dK = d G (x K)
– Si k ≤ q+1, on a :
min {d k + 1, k} ≤ min {d k + 1, q+1} ≤ q+1
– Si k ≥ q+2, on a
min {d k + 1, k} ≤ min {dG (x q + 2) + 1, k} ≤ min {q +1,k}≤ q d’où le résultat γ(G) ≤ q + 1 d’après le théorème 3
Corollaire 6 Soit G = (S , A) un graphe de degré maximum h, on a : γ(G) ≤ h+1 Preuve Il suffit de faire q = h dans l’énoncé du corollaire Remarque 4 Le théorème 3 permet parfois d’obtenir une borne supérieure du nombre chromatique plus avantageuse que celle donnée par les corollaires 1 et 2 en partant d’une k-coloration (S1, S2, … S k) définie de la façon suivante :
On prend pour S1 un ensemble stable maximal qui contient beaucoup de sommets de degrés élèves ; puis on prend pour S2 un ensemble stable maximal de S-S1 qui contient le plus possible de sommets de degrés élèves, etc… Théorème 8 (Brooks 1941) Soit G un graphe simple connexe de degré maximum h Si G, n’est ni la clique Kh+1 ni un cycle élémentaire impair, alors γ(G) ≤ h Preuve L’énoncé étant vrai pour h = 0,1,2 supposons h ≥ 3 Soit G = (X , E) un graphe tel que γ(G) = h + 1, h ≥ 3 Supposons que G ne soit pas une (h+1)clique et montrons que l’on aboutit à une contradiction . Quitte à retirer des sommets de G, on peut supposer que G est minimal avec ces propriétés.
1) Soit x0 un sommet de X. le sous-graphe G0 de G engendré par X-{x0} n’est pas une (h+1) clique ,sinon G étant annexe, il aurait un degré maximum supérieur ou égal à h+1.G étant minimal, on a γ (G0)< h+1.Puisque γ(G)=h+1, on a donc γ (G0) = h , d’ou dG (x0) = h, car si dG (x0) < h, une des h couleurs utilisées pour colorier G0 pourrait servir à colorier x0. De plus, si y1, y2,…… y h sont les h sommets adjacents à x0, ils utilisent respectivement les h couleurs α1, α2, … αh dans une h – coloration de G0
2) Pour deux couleurs αi et αj de cette coloration de G0, considérons le sous-graphe G i, j engendré par les sommets de couleurs αi et αj . Les sommets yi et yj de G sont dans la même composante connexe de G i, j , sinon on pourrait obtenir une h – coloration de G en échangeant les couleurs αi et αj sur les sommets de la composante connexe de yi dans G i, j puis en coloriant x0 avec la couleur αi
3) Montrons que la composante connexe de Gi,j contenant yi et yj est une chaîne élémentaire d’extrémités yi et yj ,yi est adjacent à un seul sommet de couleur αj , sinon on pourrait recolorier yi avec une couleur αk , αk ≠ αi , αk ≠αg non utilisée pour colorier tous les voisins de yi qui sont au plus au nombre h et colorier ensuite x0 avec la couleur αi . Ainsi, dG i ,j (yi) = 1 et de même d G i,j (yi) = 1 considérons une chaîne élémentaire allant de yi à yi dans Gi,j. soit x le premier sommet de cette chaîne avec dG i, j (x) > 2. Si, par exemple, x est un sommet de couleur αj , il y aura trois sommets de couleurs αj adjacents à x et donc, comme dG (x) ≤ h, le sommet x pourrait être recolorier avec une couleur αk , αk ≠ αi, αk ≠ αj ce qui disconnecterait yi et yj et contredirait le 2). Ainsi Gi,j est une chaîne élémentaire d’extrémités yi et yj car dG i,j ( yi ) = dG i,j ( yj ) = 1, que nous noterons u [yi, yj].
4e) Deux composantes connexes u [yi, yj] et u’ [yi, y k] de Gi ,j et Gi, k avec k≠j n’ont en commun que le point yi, car si z ≠y i était commun à ces deux composantes connexes et z serait de couleur αi et serait adjacent à deux sommets de couleurs αj et à deux sommets de couleurs αk , on aurait alors h ≥dG (z) ≥4 et il existerait une quatrième couleur α1 { αi, αj, α k} avec laquelle nous pourrions recolorier z, ce qui disconnecterait yi et yi.
5e ) G n’étant pas une (h+1) -clique, il existe parmi les sommets voisins de x0 deux sommets non adjacents entre eux y1 et y2 par exemple. Soit u [y1, y2] et u’ [y1 , y3 ] les chaînes définies au 3e), et soit x le sommet de G1, 2 adjacents à y 1. il est clair que x est différent de y2 puisque y1 et y2 ne sont pas adjacents. Si l’on échange les couleurs α 1 et α3 des sommets de u’ [y1, y3)], le sommet y1 devient de couleur α3 , y3 de couleur α1 et la nouvelle composante connexe H1,2 de couleur α1 et α2 qui contient y2, contient u [x, y2] puisque d’après le 4e) les chaînes u [y1, y2] et u’ [y1, y3] n’ont pas de sommet commun autre que y1. D’autre part, la composante connexe H2,3 de couleurs α2 et α3 qui contient y1 contient u [y1, x] puisque x est de couleur α2 et adjacent à y 1. Donc x est sommet commun aux deux composantes connexes H1,2 et H2,3 qui contredit le 4e Algorithme de recherche de nombre chromatique et application
Algorithmes de coloration de sommets de graphes
Dans ce chapitre, nous allons donner des algorithmes pour la recherche du nombre chromatique. Cependant il n’existe pas d’algorithme donnant exactement le nombre chromatique d’un graphe. Mais néanmoins ces algorithmes permettent d’obtenir une assez bonne coloration d’un graphe donné. Ceci combiné avec l’encadrement du nombre chromatique nous permet dans plusieurs cas de donner exactement le nombre chromatique d’un graphe donné.
Algorithme de WELSH et POWELL
Premier énoncé :
Etape 1
Classer les sommets du graphe dans l’ordre décroissant de leur degré, et attribuer à chacun des sommets son numéro d’ordre dans la liste obtenue.
Etape 2
En parcourant la liste dans l’ordre, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur.
Etape 3
S’il reste de sommets non colorés dans le graphe, revenir à l’étape 2, sinon , la coloration est terminée.
Deuxième énoncé :
1) Numéroter les sommets par ordre décroissant de leur degré Poser i =1(couleur) et N = {sommets non encore colorés}
2) Donner la couleur i au sommet de N qui a le plus petit numéro
3) Soit Ni ={ sommets non encore colorés non adjacents
à un sommet de couleur i}
Si Ni = Ø, poser N = Ni et aller en (2)
4) Poser N = {sommets non encore colorés }
Si N = Ø, poser i = i +1 (couleur suivante ) et aller en (2 )
Sinon on a une coloration en i couleurs
Table des matières
INTRODUCTION
PROBLEMATIQUE
METHODOLOGIE
CHAPITRE 1 : GENERALITES SUR LES GRAPHES 4
I- Concepts élémentaires de base
II- Opération sur les graphes
II-1 Elimination de sommets
II-2 Elimination d’arêtes
II-3 Regroupement de sommets ou contraction
CHAPITRE 2 : CARACTERISTIQUES DE GRAPHES 15
I- Connexité dans un graphe (définitions et propriétés).
II- Graphes particuliers
II-1 Graphes réguliers
II-2 Graphes complets
II-3 Graphes bipartis
II-4 Graphes bipartis complets
III- Graphes planaires.
IV- Homeophisme de graphes et théorème de Kuratowski
CHAPITRE 3 : NOMBRE CHROMATIQUE DE SOMMETS DE GRAPHES 26
I- Ensemble stable ou indépendant
I-1 Définitions
I-2 Majoration et minoration
II- Nombre chromatique
II-1 Coloration de sommets
II-2 Graphe p- chromatique ou graphe p- colorable
II-3 Nombre chromatique.
II-4 Nombre chromatique de quelques graphes particuliers
II-5 Encadrement du nombre chromatique
II-5-1 Minoration
II-5-2 Majoration
CHAPITRE 4 : ALGORITHMES DE RECHERCHES DE NOMBRE CHROMATIQUES ET APPLICATIONS 45
I- Algorithmes de coloration de sommets de graphes
I-1 Algorithmes de WELSH et POWELL
I-2 Algorithme utilisant les ensembles stables
I-3 Principes des reliements – contraction. Principe
de la séparation des pièces
II- Applications
CONCLUSION
