Outils et techniques de la techniques de la théorie des graphes avancée et appliquée

U.S.T.H.B.     /      FACULTE DE MATHEMATIQUES  /      DEPARTEMENT  DE R.O.        

                MASTER  2MIR  /  ANNEE 2016/2017

OUTILS ET TECHNIQUES DE LA THEORIE DES GRAPHES AVANCEE ET APPLIQUEE I

FONDEMENTS DES GRAPHES PARFAITS

1 )Introduction

Introduite dans les années 60 par Claude Berge, la notion de graphe parfait   a depuis ´et´e d’une grande importance en  théorie des graphes.

De nombreuses classes sont en effet incluses dans la classe des graphes parfaits. Elle permet de généraliser un certain nombre de résultats connus sur ces classes  particulières.

Les graphes  parfaits ont une importance majeure  du fait des nombreuses applications dans le monde réel.

Les graphes parfaits ont´et´e étudiés intensivement dans le but de prouver les deux fameuses conjectures (faible et  forte) des graphes parfaits.

L’étude des graphes parfaits contribue de plus en plus à la résolution de nombreux problèmes du monde réel. La notion de graphe parfait intervient dans des domaines très variés tel que la communication, l’information, la planification des périodes horaires (examens, réunions,…etc.) ou les services municipaux.

Les recherches qui s’orientent vers l’étude de cette notion consistent principalement à mettre en évidence de nouvelles classes de graphes parfaits, et dont l’intérêt pratique serait d’élargir le champ des modèles de graphes qui reflètent des problèmes du monde réel et ayant cette propriété grâce à laquelle on pourrait les résoudre. Par exemple, dans la théorie de l’information, lorsqu’il s’agit d’enrichir le code de transmission, il est inutile de chercher à augmenter la taille du code en utilisant  plus de mots (pour une taille donnée des mots constituants le code) si le graphe de confusion est faiblement [pic 1]parfait  (Un graphe G est dit faiblement [pic 2]parfait si [pic 3].

Dans le problème de l’affectation des fréquences des radios mobiles, on peut éviter lors de contacts radios entre deux zones, les interférences engendrées par des fréquences communes aux deux bandes attribuées à ces zones tout en minimisant la longueur de ces fréquences, il suffit pour cela et dans le cas des graphes faiblement [pic 4]parfait de calculer le nombre chromatique du graphe représentatif. Dans certains cas, la résolution d’un problème revient à calculer le nombre chromatique du graphe qui le modélise, où le cardinal de la clique maximum est plus facile à calculer, il serait donc intéressant de savoir si ce graphe est faiblement [pic 5]parfait auquel cas ces deux nombres sont égaux. Dans le problème des graphes des tournées, Tucker a proposé de calculer le cardinal de la clique maximum du graphe des tournées, en déduire son nombre chromatique, et ainsi l’affectation des tournées aux différents jours de la semaine, mais cette démarche est correcte uniquement lorsque le graphe des tournées est faiblement [pic 6]parfait. Ceci implique l’intérêt de la reconnaissance des graphes faiblement [pic 7]parfait.

Il peut sembler que les objectifs des travaux considérables menés depuis fort longtemps sur les graphes parfaits sont purement théoriques, mais en fait chaque étude est motivée par des interrogations d’ordre pratique qui stimulent leur développement, et les rendent efficaces face à de nombreux problèmes du monde réel.

2 )  Premières définitions et quelques conjectures célèbres  

2.1        Quelques rappels

Définitions

On dit qu’un graphe G=(V,E) est simple s’il ne possède pas de boucle et qu’il n’a pas d’arêtes multiples.

L’ensemble de tous les voisins d’un sommet u d’un graphe G=(V,E) est appelé le voisinage de u et sera noté par NG(u).

L’ordre d’un graphe G est le nombre n d’éléments de V.

Le degré d’un sommet u est le nombre d’arêtes incidentes à u dans G, il sera noté dG(v).

Etant donné un sous ensemble X de V, on appelle sous- graphe de G induit par X, le graphe [pic 8]où  [pic 9].

Etant donné un sous ensemble [pic 10] de E, on appelle graphe partiel de G engendré par [pic 11], le graphe [pic 12]

Un sous graphe H de G, diffèrent de l’ensemble vide et de G est dit sous graphe propre de G.

Définition d’un stable dans un graphe

Soit G un graphe simple. On dit que S ⊆ V est un stable si∀x; y ∈ S;   (x,y)) ∉ E.

Définition du nombre de stabilité

Soit G un graphe simple. On note α(G) la taille maximale d’un stable de G.

Définition d’une clique dans un graphe

Soit G=(V,E) un graphe simple. On dit que K⊆V est une clique de G si ∀x; y∈K; (x,y)∈ E.

Définition de la taille de la plus grande clique

Soit G un graphe simple. On note ω(G) la taille maximale d’une clique de G, appelée aussi le nombre de clique

2.2 ) Autres  définitions

Définition de la coloration

Soit G=(V,E) un graphe simple. Une coloration de G est une partition de V en stables.

Définition du nombre chromatique

Soit G un graphe simple. On appelle nombre chromatique de G et on note χ(G) le cardinal minimum d’une coloration de G.

Définition de la classe des graphes parfaits

On définit la classe des graphes parfaits comme la classe des graphes G tels que pour tout H sous-graphe de G, alors ω(H)=χ(H )

Remarques :

- Un graphe G est dit faiblement χ-parfait si ω (G)=χ(G) ;

...