Les sommets appartenant à tout ou a aucun Y2-ensemble et Implémentation.

Abstract

Soit G = (V,E) un graphe simple d'ordre n où V est l'ensemble des sommets et E est l'ensemble des arêtes. Le problème de domination consiste à trouver un ensemble de sommets D tel que chaque sommet de V D admet au moins un voisin dans D qu'on appelle ensemble dominant, le cardinal minimum d'un ensemble dominant d'un graphe G est noté y(G) dit nombre de domination. D'une manière plus générale, pour un entier k 21, un ensemble k-dominant D d'un graphe G est un ensemble de sommets tel que tout sommet de V D admet au moins k voisins dans D. Le nombre de k-domination Yr (G) est la cardinalité minimum d'un ensemble k-dominant de G. Dans ce mémoire on a étudié le paramètre Y2(G) dans les graphes, on a élaboré et implémenté un algorithme qui permet de reconnaître les sommets qui appartiennent à tout ou à aucun Y2-ensemble dans un arbre. Suite à cette reconnaissance et dans le même logiciel qu'on a établi on peut spécifier la nature d'un arbre donné : arbre excellent, arbre recommandable, arbre indésirable, arbre juste, et même si l'arbre admet un Y2-ensemble unique.