Algorithmique et Programmation Projet Algorithme“Measure and Conquer”pour Maximum Independent Set

Algorithmique et Programmation Projet : Algorithme“Measure and Conquer”pour Maximum-Independent-Set Ecole normale superieure Departement d'informatique 2011-2012 1 Contexte On s'interesse au probleme des gardiens de musee. Un musee est schematiquement forme de couloirs, ou des peintures sont accrochees. Les couloirs doivent etre surveilles par des gardiens. Quand un gardien est positionne au croisement de plusieurs couloirs, il surveille tous les couloirs attenants. Les gardiens du musee en question, tout comme la direction, ont a coeur que la surveillance ait effectivement lieu. Pour assurer le coup, la direction a utilise un algorithme glouton pour assigner les gardiens a des croisements. Cependant, il semble aux gardiens qu'ils sont legerement en sur-effectif, et que certains d'entre eux pourraient faire la sieste ou sortir pendant que les autres assurent la surveillance. C'est une nouvelle illustration du fait qu'un travailleur efficace est un faineant malin. Ils cherchent donc a determiner le nombre strictement minimal de gardiens necessaires a la surveillance du musee, afin de profiter davantage de la vie. Formellement, les couloirs du musee sont les aretes d'un graphe, et le probleme consiste a placer des gardiens sur les sommets de ce graphe de telle sorte que chaque arete soit attenante a un gardien (au moins). On cherche a placer le moins de gardien possible.

• clique


• taille


• return max


• maximum independent


• gardien


• i˜ ?