Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
un des théorèmes les plus populaires de la
théorie des graphes est le théorème des quatre couleurs
dont une partie de la démonstration, achevée dans les années 70, a
été faite par ordinateur, plus d'un siècle après la conjecture. Ce
théorème stipule que toute carte planaire (en gros, la carte des
départements français) peut se colorier à l'aide de seulement
quatre couleurs de sorte que deux zones adjacentes (par un côté)
aient deux couleurs différentes.
Au cours de son existence, cette conjecture a apporté de nouveaux
outils afin d'appréhender les colorations de graphes et de
cartes. L'un d'eux est le polynôme chromatique d'un graphe: il
donne le nombre de façons de colorier un graphe donné avec
c couleurs. Ce polynôme possède un certain nombre de
propriétés. En particulier, le nombre minimal de couleurs
nécessaires pour colorier les sommets d'un graphe (nombre
chromatique) est égal au plus petit entier positif tel que le
polynôme est non nul. L'étude du polynôme chromatique s'est
révélé au cours du temps un domaine à part entière, un peu
déconnecté du problème initial. Par exemple, on s'est beaucoup
intéressé à la localisation des zéros non entiers de ce
polynôme. En utilisant le théorème de Brooks, on peut calculer de
manière assez simple le polynôme chromatique. Malheureusement, ce
calcul nécessite un nombre exponentiel d'étapes. Le problème de la
recherche du nombre chromatique étant NP-Dur, il y a peu
d'espoir de trouver des méthodes efficaces dans tous les cas.
Dans le cadre de ce sujet, nous voudrions améliorer certaines
techniques mises au point précédemment. Diverses fonctionnalités
peuvent être intégrées, on peut citer par exemple:
la spécialisation d'une fonction de choix centrale lors de
l'algorithme précédent;
la combinaison de l'algorithme précédent avec d'autres techniques
afin d'appréhender le calcul du polynôme chromatique pour une famille
plus grande de graphes.
Travail demandé:
Il s'agira dans un premier temps
d'appréhender les diverses méthodes de calcul de ce polynôme données
dans la littérature, ainsi que l'étude menée précédemment. Dans un
second temps, l'étude portera sur le point choisi par le groupe.
Nombre de personnes:
1 ou 2 intéressés par la théorie
des graphes et l'algorithmique que l'on peut développer sur ces
structures. Les problèmes seront abordés de manière progressive.
Bibliographie
C. Berge, "Graphes et Hypergraphes", Dunod.
B. Jackson, "Zeros of chromatic and Flow Polynomials of
Graphs", 2002.
K. Nguyen, A. Vieilleribière, S. Lebresne, "Polynôme
Chromatique", TER STage 2002-2003
Outils, Langages utilisés
Langage de programmation permettant de coder des graphes et des
polynômes (au choix des intéressés); une préférence sera CAML
qui a servi pour le développement de la première phase.