This HTML5 document contains 28 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

n2:id

rdf:type

frbr:Work rdac:C10001

marcrel:ths

n6:id n17:id n18:id

marcrel:aut

n15:id

dc:subject

Thèses et écrits académiques Galois, Correspondances de NFL réactions No Free Lunch Correspondance de Galois Décomposition en cliques maximales NFL article initial Euler, Polynômes d' Polynôme chromatique

skos:prefLabel

No Free Lunch et recherche de solutions structurantes en coloration

dcterms:language

n22:fra

dcterms:subject

n4:id n19:id n20:id

dc:title

No Free Lunch et recherche de solutions structurantes en coloration

marcrel:dgg

n21:id

skos: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

Text

n12:P1001

n13:T1009

rdaw:P10219

2010

rdau:P60049

n10:1020