GRAPHES PARFAITS THÉORÈME FORT DES

Carte mentale

Élargissez votre recherche dans Universalis

Vous organisez un colloque dans lequel plusieurs conférences sont données simultanément (dans des salles différentes et à des horaires imposés par les orateurs) et vous cherchez à occuper le moins de salles possibles (car vous devez les louer). Une méthode permettant de réaliser un tel planning consiste à construire un graphe G dans lequel les conférences seront représentées par des sommets tandis que le fait que deux conférences se tiennent, au moins en partie, en même temps sera symbolisé par une arête reliant les deux sommets associés.

On cherche à affecter une salle (repérée par un numéro) à chaque conférence, de telle sorte que deux conférences adjacentes (reliées par une arête) ne soient pas dans la même salle. Une telle affectation est appelée une coloration et le nombre de couleurs est au moins égal au plus grand nombre W(G) de sommets de G deux à deux adjacents. Par exemple, un cycle (graphe dont les sommets sont reliés uniquement à leur prédécesseur et leur successeur) est coloriable en 2 (nombre pair de sommets) ou 3 (nombre impair de sommets) couleurs.

Le graphe précédent est un graphe d'intervalle et fait partie de la famille des graphes parfaits introduite par le Français Claude Berge (1926-2002) au début des années 1960. Ces graphes sont ceux pour lesquels tout sous-graphe induit H (défini par des sommets et toutes les arêtes qui les relient dans G) est coloriable avec le nombre minimum de couleurs W(H). Ils sont connexes si on peut toujours passer d'un sommet à n'importe quel autre en suivant une (ou plusieurs) arête(s). En 1960, Claude Berge énonça les deux conjectures suivantes : 1. Un graphe est parfait si, et seulement si, son complémentaire (graphe ayant les mêmes sommets et toutes les arêtes complémentaires) l'est. 2. Un graphe est parfait si, et seulement si, il ne contient ni cycle impair, ni complément de cycle impair, sur au moins 5 sommets (un tel graphe est maintenant appelé un graphe de Berge).

La première conjecture (dite « faible ») fut démontrée en 1972 par le Hongrois László Lovász, tandis [...]

1  2  3  4  5
pour nos abonnés,
l’article se compose de 2 pages

Écrit par :

  • : maître de conférences en informatique L.I.U.M., université du Maine (Étsts-Unis)

Classification

Pour citer l’article

Vincent BARRÉ, « GRAPHES PARFAITS THÉORÈME FORT DES », Encyclopædia Universalis [en ligne], consulté le 06 mai 2021. URL : https://www.universalis.fr/encyclopedie/theoreme-fort-des-graphes-parfaits/