Nombre domatique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, le nombre domatique d'un graphe est son nombre maximum d'ensembles dominants disjoints deux à deux. Le problème du nombre domatique est de déterminer, en fonction d'un graphe G et d'un entier naturel k, si le nombre domatique de G est supérieur ou égal à k. C'est un problème NP-complet.

Exemple[modifier | modifier le code]

Le nombre domatique de ce graphe vaut au moins 3.

Dans le graphe ci-contre, les trois ensembles de sommets (associés à chaque couleur) sont disjoints deux à deux, et dominants (par exemple pour l'ensemble jaune : tout sommet est soit jaune, soit voisin d'un jaune). Le nombre domatique du graphe vaut donc au moins 3 (en fait, il est exactement égal à 3).

Définitions équivalentes[modifier | modifier le code]

Le nombre domatique de G est le plus grand entier n pour lequel il existe une partition de l'ensemble des sommets en n ensembles dominants.

Le problème du nombre domatique pour G et k revient à déterminer s'il existe k ensembles dominants disjoints deux à deux.

Complexité[modifier | modifier le code]

Le problème du nombre domatique a été prouvé NP-complet par réduction mutuelle avec le problème 3SAT.

Références[modifier | modifier le code]