No Free Lunch Et Recherche de Solutions Structurantes En Coloration » książka
No Free Lunch Et Recherche de Solutions Structurantes En Coloration
ISBN-13: 9783841782564 / Francuski / Miękka / 2018 / 264 str.
Nous prA(c)sentons les thA(c)orA]mes du No Free Lunch de D.H. Wolpert et W.G. Macready (1997) et analysons les travaux essentiels qui ont suivi. Convaincus dA]s lors de l'intA(c)rAat d'une approche globale des problA]mes, de la nA(c)cessitA(c) de rechercher des propriA(c)tA(c)s gA(c)nA(c)rales, et spA(c)cialement des invariances par symA(c)tries, nous mettons en oeuvre cette mA(c)thode en coloration des graphes simples et non orientA(c)s. Nous faisons A(c)merger la notion de dA(c)composition d'un graphe en cliques maximales puis celle de suites constructives qui permettent de reconstruire un graphe A partir de ses composants A(c)lA(c)mentaires - les primary cliques -, A(c)quivalents des nombres premiers pour les entiers. Nous produisons un algorithme principal et deux cas singuliers. Ils fournissent une partition de l'ensemble des colorations valides du graphe A(c)tudiA(c) et son polynAme chromatique de maniA]re formelle, indA(c)pendamment du nombre de couleurs disponibles. Nous A(c)tablissons une correspondance de Galois entre colorations valides et sous-graphes engendrA(c)s par des familles emboA(R)tA(c)es de cliques maximales pourvu qu'elles soient des dA(c)compositions complA]tes de sous-graphes croissants du graphe total: phA(c)nomA]ne typiquement galoisien
Nous présentons les théorèmes du No Free Lunch de D.H. Wolpert et W.G. Macready (1997) et analysons les travaux essentiels qui ont suivi. Convaincus dès lors de lintérêt dune approche globale des problèmes, de la nécessité de rechercher des propriétés générales, et spécialement des invariances par symétries, nous mettons en oeuvre cette méthode en coloration des graphes simples et non orientés. Nous faisons émerger la notion de décomposition dun graphe en cliques maximales puis celle de suites constructives qui permettent de reconstruire un graphe à partir de ses composants élémentaires - les primary cliques -, équivalents des nombres premiers pour les entiers. Nous produisons un algorithme principal et deux cas singuliers. Ils fournissent une partition de lensemble des colorations valides du graphe étudié et son 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 quelles soient des décompositions complètes de sous-graphes croissants du graphe total: phénomène typiquement galoisien !
Czytaj nas na:
KrainaKsiazek.PL - Księgarnia Internetowa
