No Free Lunch Et Recherche de Solutions Structurantes En Coloration

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 l'int?r?t d'une 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 d'un 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 l'ensemble 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 qu'elles soient des d?compositions compl?tes de sous-graphes croissants du graphe total: ph?nom?ne typiquement galoisien !

Author: Collectif

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 264 pages

Binding: Paperback or Softback

ISBN-10: 3841782566

ISBN-13: 9783841782564