Nombre achromatique

Nombre achromatique

En théorie des graphes, une coloration complète est l'opposé d'une coloration harmonieuse en ce sens que c'est une coloration des sommets dans laquelle toute paire de couleurs apparait au moins sur une paire de sommets adjacents. Le nombre achromatique ψ(G) d'une graphe G est le nombre maximum de couleurs possibles dans une coloration complète de G. Trouver ψ(G) est un problème d'optimisation. Le problème de décision pour le problème de coloration complète peut être exprimé ainsi :

INSTANCE: un graphe G = (S,A) et un entier positif k
QUESTION: existe-t-il une partition de S en au plus k ensembles disjoints S_1,S_2,\ldots,S_k telle que chaque Si est un ensemble indépendant pour G et telle que pour chaque paire d'ensembles distincts S_i,S_j,S_i \cup S_j ne soit pas un ensemble indépendant.

Déterminer le nombre achromatiques est NP-difficile ; déterminer s'il est inférieur à un nombre donné est NP-complet, comme l'ont montré Yannakakis et Gavril en 1978 par une transformation depuis le problème minimum maximal matching. Le problème reste NP-complet même si on le restreint aux graphes qui sont le complément d'un graphe biparti (c’est-à-dire d'un graphe qui n'a pas d'ensemble indépendant de plus de deux sommets).

Le problème d'optimisation est approximable en O\left(|S|/\sqrt{\log |S|}\right)

Références

  • Michael R. Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979. ISBN 0-7167-1045-5 A1.1: GT2, pg.190.

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Nombre achromatique de Wikipédia en français (auteurs)

Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Nombre Achromatique — En théorie des graphes, une coloration complète est l opposé d une coloration harmonieuse en ce sens que c est une coloration des sommets dans laquelle toute paire de couleurs apparait au moins sur une paire de sommets adjacents. Le nombre… …   Wikipédia en Français

  • Nombre d'Abbe — En optique, et plus particulièrement en lunetterie, le nombre d Abbe ou constringence d un verre optique sert à en déterminer la dispersion, c est à dire la variation de l indice de réfraction avec la longueur d onde. Il quantifie l aberration… …   Wikipédia en Français

  • Graphe de Clebsch — Représentation du graphe de Clebsch Nombre de sommets 16 Nombre d arêtes 40 Distribution des degrés 5 régulier Rayon …   Wikipédia en Français

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

  • Liste De Problèmes NP-Complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Liste de problemes NP-complets — Liste de problèmes NP complets Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets,… …   Wikipédia en Français

  • Liste de problèmes np-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problèmes de la décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive …   Wikipédia en Français

  • Constringence — Nombre d Abbe En optique, et plus particulièrement en lunetterie, le nombre d Abbe ou constringence d un verre optique sert à en déterminer la dispersion, c est à dire la variation de l indice de réfraction avec la longueur d onde. Il quantifie l …   Wikipédia en Français

  • Diagramme d'Abbe — Nombre d Abbe En optique, et plus particulièrement en lunetterie, le nombre d Abbe ou constringence d un verre optique sert à en déterminer la dispersion, c est à dire la variation de l indice de réfraction avec la longueur d onde. Il quantifie l …   Wikipédia en Français

  • fuseau — [ fyzo ] n. m. • XIIe; de l a. fr. fus; lat. fusus 1 ♦ Petit instrument en bois tourné, renflé au milieu, effilé aux deux extrémités, qui sert à tordre et à enrouler le fil, lorsqu on file à la quenouille. Fil d un fuseau. ⇒ fusée. Le fuseau des… …   Encyclopédie Universelle

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”