COLORATION MINIMALE DE GRAPHE OU DETERMINATION DU NOMBRE CHROMATIQUE

COLORATION MINIMALE DE GRAPHE OU DETERMINATION DU NOMBRE CHROMATIQUE

Issue des travaux du mathématicien Suisse Euler , la théorie des graphes a fourni son premier résultat formel avec la résolution du problème mathématique historique de la traversée des ponts de Königsberg : la question à l’époque était de passer par sept ponts et revenir au point de départ sans traverser un pont deux fois ( chaque pont ne pouvait être parcouru une fois et une seule ) ; Euler proposa en 1736 une réponse satisfaisante à la question . La théorie des graphes s’est ensuite développée dans la deuxième moitié du 19e siècle avec les mathématiciens Hamilton , Headwood , Kempe , Kirchhoff, Peterson , Tait… ; mais a connu un boom au début du 20e siècle avec les recherches de König , Hall , Kuratowski , Whitney , Erdös , Tutte, Edmond , Berge, Lovasz , Seymour , et beaucoup d’autres . La théorie des graphes est devenue aujourd’hui l’un des domaines mathématiques le plus appliqué. Elle constitue un outil de modélisation et de résolution de problèmes réels assez complexes . De plus les chercheurs en théorie des graphes s’attachent souvent à travers des algorithmes efficaces pour résoudre un problème donné . Un grand problème classique de la théorie des graphes est la coloration de graphes qui a des applications nombreuses : -Etablissement d’emploi du temps -Programmation de conférences -Gestion des ressources partagées Ils posent la détermination de la coloration minimale nécessaire d ’un gr aphe ou du nom bre chromatique . C e qui constitue l ’objet de ce m émoire . Il est subdivisé en trois chapitres . Le premier chapitre introduit les éléments de théorie des graphes . Les définitions de graphes , l a manipulation de graphes , les graphes connexes , les graphes planaires y sont présentés . Le second chapitre traite la c oloration de graphes , c ’est à dire la coloration de sommets , la coloration d’arêtes et la coloration de faces. Le troisième ch apitre étudie les heuristiques séquentielles , la méthode Backtrack , la méthode de recuit simulé , et la méthode taboue qui sont des méthodes de coloration qui pe rmettent de déterminer le nombre chromatique . C e dernier chapitre fournie également une comparaison des résultats des différentes méthodes de coloration proposées. 

Eléments de théorie des graphes

Graphes

Définition 1.1.1 Un graphe G=(X,E) est un couple composé : -d’un ensemble X dont les éléments sont appelés sommets ou nœuds ou extrémités -d’un ensemble E⊂XxX dont les éléments sont appelés arcs si l’on tient compte de l’ordre des éléments de X ; sinon ils sont appelés arêtes . Le nombre d’éléments de X est appelé l’ordre du graphe . Définition 1.1.2 Un graphe G=(X,E) est dit orienté si les éléments de E sont orientés . Ils sont des arcs . Définition 1.1.3 Un graphe G=(X,E) est dit non orienté si les éléments de E sont non orientés . Ils sont des arêtes . Définition 1.1.4 Un graphe G=(X,E) est dit mixte si certains éléments de E sont orientés tandis que d’autres sont non orientés . Notons que pour la représentation graphique d’un graphe les sommets sont représentés par des points , les arêtes par des segments de droites et les arcs par des flèches . Exemples 1.1.1 Dans la figure1 ci-dessous -le graphe G=(X,E) est non orienté avec X={x1,x2,x3,x4,x5,x6} et E={(x1,x4),(x2,x5),(x4,x3)} . -le graphe H=(X,E) est orienté avec X={y1,y2,y3,y4,y5,y6}et E={(y1,y4),(y4,y3),(y2,y5),(y5,y6)} . -le graphe I=(X,E) est mixte x1 x2 x3 y1 y2 y3 z1 z2 z3 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● x4 x5 x6 y4 y5 y6 z4 z5 z6 G H I Graphe non orienté Graphe orienté Graphe Mixte Figure 1 3 Dans toute la suite , sans précision nous entendrons par le terme graphe : un graphe simple non orienté . Définition 1.1.5 Soient G1=(X1,E1) et G2=(X2,E2) deux graphes tels que X1 ⊂ X2 et E1⊂ E2 , on dit que G1 est sous-graphe de G2 . Exemple 1.1.2 Dans la figure ci-dessous G1 est un sous-graphe de G2 car X1 ⊂ X2 et E1 ⊂ E2 x1 x1 x4 ● ● ● ● ● ● ● x2 x3 x 2 x3 G1 G2 Figure 2 Définition 1.1.6 Soit G=(X,E) un graphe , G est dit complémentaire de G si G =(X,Ē) avec Ē le complémentaire de E . Exemple 1.1.3 Les graphes G1et G2 de la figure3 ci-dessous sont complémentaires. x1 x2 x1 x2 x3 x5 x3 x5 x4 x6 x4 x6 x7 x8 x7 x8 G1 G2 Figure 3 4 Définition 1.1.7 Un graphe G=(X,E) à n sommets et 0 arête est appelé graphe nul ; E est vide . Exemple 1.1.4 Le graphe G de la figure 4 est constitué de points isolés : c’est un graphe nul x2 x1● ● ●x5 x3● ●x4 x6● x7● ●x8 G Figure 4 Définition 1.1.8 Soit G=(X,E) un graphe , si a=(x1,x2) est une arête de E on dit que a est incidente aux extrémités x1 et x2. (a incidente à x1 et a incidente à x2 ) . Exemple 1.1.5 Le sommet x1 du graphe G1 de la figure 2 est incidente aux arêtes (x1,x2) et (x1,x3) . Définition 1.1.9 Soit G=(X,E) un graphe et x un sommet de X , le nombre d’arête incident à x est appelé le degré de x et est noté d(x). On définie alors les fonctions suivantes : Λ (G)= min{d(x), x∈X} : degré de sommet le plus bas de G . ∆(G)= max{d(x), x∈X} : degré de sommet le plus haut de G . Remarque 1.1.1 Si le sommet x d’ un graphe G=(X,E) est tel d(x) =0 alors le sommet x est dit isolé : x n’a aucun lien avec les autres sommets . Si d(x)=1 alors x est dit pendant . Si Λ(G )=0 , G possède un point isolé alors que si Λ(G )=1 , G possède un point pendant . Si ∆(G) =0 alors G est le graphe nul , i l ne possède pas d’arête tandis que si ∆(G) = 1 , G possède une seule arête ou des arêtes dispersées . Exemple 2.1.6. Le sommet x1 du graphe G1 de la figure 2 est incident aux arêtes (x1,x2) et (x1,x3) ; ce même sommet a pour degré d(x1)=2 . Le sommet x3 du graphe G de la figure1 est pendant tandis que le sommet x6 de ce même graphe est isolé . Définition 1.1.10 Soit un graphe G=(X,E) de n sommets et m arêtes. On appelle suite des degrés de G la suite croissante {d1 , d2 , … , dn} telle que pour chaque di , il existe un sommet x∈X justifiant d(x)=di . Exemple 1.1.7 Le graphe G2 de la figure 2 a pour suite des degrés : (3,2,3,2) 5 Définition 1.1.11 Soit G=(X,E) un graphe , G est dit régulier de degré d si ses sommets ont un même degré d . Exemple 1.1.8 Le graphe G de la figure 5 ci-dessous a pour suite des degrés (3,3,3,3,3,3) : c’est un graphe régulier . x1 x2 x3 x4 x5 x6 Figure 5 Définition 1.1.12 Soient G=(X,E) un graphe et x1 , x2 deux éléments de X tels que (x1,x2) ∈E alors x1 et x2 sont dits adjacents . Exemple 1.1.9 Les sommets x1 et x2 du graphe G de la figure5 sont adjacents . Définition 1.1.13 Soit G=(X,E) un graphe et x un élément de X , l’ensemble de tous les éléments de X ayant un lien avec x est appelé voisinage de x et on note cet ensemble N(x) . On a N(x)⊂X . On peut aussi définir le voisinage d’un ensemble X’⊂X : c’est l’ensemble de tous les éléments de X ayant au moins un lien avec un élément de X’ . On le note N(X’) . Exemple 1.1.10 Dans la figure 5 pour le graphe G on a N(x1)={x2,x3} et N({x1 ,x2})={x1,x2,x3,x4,x5,x6} Théorème 2.1.1 (Handshaking Théorème) Soit G=(X,E) un graphe de n sommets m arêtes on a alors 2m =∑d(x), x∈X . Preuve d(x) est le nombre d’arêtes de E incidentes à x ; comme chaque arête (x1 ,x2) comprend deux sommets x1 , x2 ainsi l’arête est comptée 2 fois dans la sommation ∑d(x) , x∈X , par suite le nombre d’arêtes m=∑d(x)/2,x∈X; d’où 2m=∑d(x),x∈X .

Manipulation de graphes

Union et addition de graphes

Définition 1.2.1 Soient G1=(X1 ,E1) et G2=(X2,E2) deux graphes définis tels que X1 ∩ X2=φ alors on a : i) G1∪ G2=(X1∪X2, E1 ∪E2) ii) G1+G2=(X1∪X2, E1∪E2∪E12) avec E12={(x1,x2) /x1∈X1,x2∈X2} 6 Exemple 1.2.1 Union et addition de graphes x1 x2 x1 x2 x1 x2 x1 x2 x3 x4 x3 x4 x3 x4 x3 x4 G1 G2 G1UG2 G1+G2 Figure 6 1.2.2 Soustraction de sommets Définition 1.2.2 Soient G=(X,E) un graphe, x1∈X et X1⊂X on a : i) G-x1=(X-x1 ,E-E1) avec E1ensemble des arêtes incidentes à x1 ii) G-X1=(X-X1 , E-E1*) avec E1* ensemble des arêtes incidentes à X1 1.2.3 Soustraction d’arêtes Définition 1.2.3 Soient G=(X,E) un graphe , e une arête de E et E’ un sous ensemble de E on a i) G-e=(X, E-e) ii) G-E’=(X, E-E’) .