Accueil🇫🇷Chercher

Nombre domatique

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

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

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é

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

Références

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.