COLORATION MINIMALE DE GRAPHE OU DETERMINATION DU NOMBRE CHROMATIQUE

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)  

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’) 7 Exemple 1.2.2 Soustraction de sommets et d’arêtes x1 x2 x1 x2 x1 x2 x5 x6 x6 x3 x4 x3 x4 x3 x4 G G-{x5} G-{x5,x6} x1 x2 x1 x2 x5 x6 x5 x6 x3 x4 x3 x4 G-{(x5,x6)} G-{(x1,x5) , (x5,x6)} Figure 7 1.2.4 Regroupement de sommets Définition 1.2.4 Soit G=(X,E) un graphe , e=(x1,x2) une arête de E et H un sous ensemble de G i) Ge est le graphe obtenu en éliminant l’arête e=(x1,x2) du graphe G et en joignant les sommets x1 et x2 . ii) GH est le graphe obtenu en prenant le sous graphe H de G comme un seul sommet de G .