Identifiant pérenne de la notice : 218120133
Notice de type
Notice de regroupement
Note publique d'information : Nous présentons d'abord les théorèmes du No Free Lunch en nous basant sur le papier
de D.H. Wolpert et W.G. Macready (version IEEE 1997) mais aussi les multiples réactions
que ces résultats ont provoquées dans la communauté de l'optimisation. Convaincus
dès lors de l'intérêt d'une approche globale des problèmes et de la nécessité de la
recherche de propriétés générales - et spécialement des invariances par symétries
-, nous tentons ensuite de mettre en oeuvre cette méthode dans le cadre de la coloration
de graphes simples et non orientés. Ce champ est retenu en raison de son intérêt propre,
mais aussi pour son caractère de modèle fécond dans de multiples problèmes d'optimisation.
Nous faisons émerger la notion de décomposition d'un graphe en cliques maximales et
celle de suites constructives qui permettent de reconstruire un graphe à partir de
ses composants élémentaires (primary cliques), véritables équivalents des nombres
premiers pour les entiers naturels. Nous produisons un algorithme principal et en
étudions deux cas singuliers; ensemble ils fournissent une partition de l'ensemble
des colorations valides du graphe étudié. Par suite nous retrouvons le polynôme chromatique
de manière formelle, indépendamment du nombre de couleurs disponibles. Nous établissons
une correspondance de Galois entre colorations valides et sous-graphes engendrés par
des familles emboîtées de cliques maximales pourvu qu'elles soient des décompositions
complètes de sous-graphes croissants du graphe total.
Note publique d'information : First we will introduce the No Free Lunch theorems by basing our arguments on D. H.
Wolpert and W.G. Macready's articles (1997 EEEI version) but also on the numerous
reactions those results produced in the community of optimization. As the global approach
to the problems and the necessity of searching for general characteristics appeared
to us as the most logical point to focus on, we will then attempt to make use of this
method for simple and non oriented graphs. This field has been chosen because first
it was a very interesting case to study and then because of its ability at multiplying
in the numerous problems of optimization. We will bring up the notion of a graph's
decomposition into maximal cliques as well as the constructive series' one which is
able to reconstruct a graph from its primary cliques- as prime numbers would for natural
numbers. Next we will produce a main algorithm and we will study two peculiar cases
which, altogether, supply a partition of a set the studied graph's proper coloring.
Then we will find the chromatic polynomial through a formal way, regardless of the
number of available colours. We will draw up a Galois connection between fitted coloring
and subgraphs generated by embedded families of maximal cliques provided that they
are the whole decomposition of growing subgraphs from the entire graph.