| Attributes | Values |
|---|
| type
| |
| Thesis advisor
| |
| Author
| |
| dc:subject
| - Thèses et écrits académiques
- Euler, Polynômes d'
- Galois, Correspondances de
- Correspondance de Galois
- Décomposition en cliques maximales
- NFL article initial
- NFL réactions
- No Free Lunch
- Polynôme chromatique
|
| preferred label
| - No Free Lunch et recherche de solutions structurantes en coloration
|
| Language
| |
| Subject
| |
| dc:title
| - No Free Lunch et recherche de solutions structurantes en coloration
|
| Degree granting institution
| |
| note
| - 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.
- 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.
|
| dc:type
| |
| http://iflastandar...bd/elements/P1001
| |
| rdaw:P10219
| |
| has content type
| |
| is primary topic
of | |
| is rdam:P30135
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
