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

...

- Autrement dit, un graphe est parfait si tout sous graphe induit est faiblement χ-parfait ;

2.3) Les théorèmes des graphes parfaits

Théorème en 1971 ( ?Conjecture faible des graphes parfaits en 1960 ).

G parfait si et seulement si G¯ parfait

Enoncé par C.Berge (en 1960), ce th´eor`eme a été r´esolu en 1971 par Laslo Lovasz. !!!.

Remarques :

- Avec l’énoncé original de la CFGP, le théorème précédent s’énonce comme suit : G est χ-parfait si et seulement si G est α-parfait ;

- Depuis, les notions χ-parfait & α-parfait sont devenues identiques.

Définition d’un trou

Soit G un graphe simple. Un trou est un cycle sans corde de longueur ≥ 4.

Théorème Fort des graphes Parfaits en 2002 ( ?Conjecture forte des graphes parfaits en 1960).

G est parfait si et seulement si ni G ni G¯ ne contiennent de trou impair.

Théorème de reconnaissance (La reconnaissance en temps polynomial des graphes parfaits).

Il existe un algorithme polynomial déterminant si un graphe simple G est parfait ou non.

Exercice 1 :Dans une université, des étudiants doivent subir un certain nombre d’épreuves en fin d’année, l’ensemble de toutes les épreuves possibles étant X. L’examen étant écrit, on désire que tous les étudiants qui doivent subir l’épreuve x le fassent simultanément. Chaque étudiant ne pouvant se présenter qu’à une épreuve au plus chaque jour. On veut organiser les examens de ces étudiants en un nombre minimum de jours.

Donner une formulation mathématique sous la forme d’un outil de la théorie des graphes.

Eléments de réponse :

Pour toute épreuve x, soit [pic 13] l’ensemble des étudiants devant subir l’épreuve x, formons le graphe [pic 14]où [pic 15] si [pic 16][pic 17]ie si les deux épreuves x et x’ ne peuvent avoir lieu simultanément. A chaque coloration des sommets de ce graphe correspond une affectation possible pour l’ensemble des épreuves et vice versa :

Le problème revient donc à chercher le nombre chromatique [pic 18]du graphe G.

Exercice 2 : Considérons le problème de l’analyse de la transmission de signaux où les sommets sont des signaux et les arêtes reliant deux signaux peuvent être distingués aisément l’un de l’autre. Chercher le plus grand ensemble de signaux clairement distinguables revient à chercher:

- Un stable maximum,

- Une clique maximum,

- Une coloration optimale

Eléments de réponse :

a) non car deux signaux d’un stable sont nécessairement confondus

b) oui, en effet :

Considérons G = (V, E) où V représente l’ensemble des signaux vi et E représente l’ensemble des arêtes (vi,vj,)/ les signaux vi &vj non confondus. Ainsi, un ensemble de signaux clairement distinguables est une clique. Par conséquent le plus grand ensemble de signaux clairement distinguables représente une clique maximum.

c) non car les éléments de la partition en χ(G)-stables représentent des signaux nécessairement confondus

Exercice 3 :

Quel est le nombre chromatique (respectivement le nombre de stabilité) :

a) du graphe complet Kn ? (justifier)

b) du cycle élémentaire sans corde Cn (n≥4) ? (justifier)

Eléments de réponse :

a) [pic 19][pic 20][pic 21]

b) [pic 22][pic 23][pic 24]

[pic 25]

[pic 26]•[pic 27][pic 28]

[pic 29]

où : [pic 30], [pic 31]

Remarque : La conjecture forte de Berge affirme que les seuls graphes imparfaits critiques sont exactement les trous et les anti-trous impairs (un imparfait critique est un graphe qui n’est pas parfait et dont tout sous graphe propre est parfait) .

3 ) La conjecture faible des graphes parfaits

Définition de la notion de multiplication de sommets

Soit G = (V, E) un graphe simple. Soit x ∈ V. Le graphe G 0 x est obtenu à partir de G en ajoutant un nouveau sommet xl connecté à tous les voisins de x. Plus généralement, si h= (h1, ..., hn) un vecteur à n-composantes où hi ∈N pour tout i et x1, x2, ..., xn sont des sommets de G, alors

h= (h1, ..., hn) un vecteur à n-composantes où hi et x1, x2, ..., xn sont des sommets de G, alors

G 0 x est obtenu en substituant à chaque xi un stable comprenant hi sommets (x1 , ..., xhi ) ; alors xs est relié à xt ssi xs et xt sont reliés dans G.

On dit que ce graphe est obtenu à partir de G par multiplication de sommets.

Définitions et propriétés [pic 32]

Soit G = (V, U) un graphe simple. On définit les propriétés suivantes

(P1) [pic 33] , ω(GA) = χ(GA)

(P2)[pic 34], α(GA) = θ(GA)

(P3)[pic 35], |A| ≤ ω(GA) α(GA)

Théorème

Soit H obtenu à partir de G par multiplication des sommets.

– Si G satisfait (P1), alors H satisfait (P1).

– Si G satisfait (P2), alors H satisfait (P2).

Le théorème suivant est très important et constitue la base du théorème des graphes parfaits,