Esercizio N. 2 Si consideri un grafo non orientato
G = (V, E). Un Insieme Dominante di vertici (in breve Insieme Dominante)
per G è un insieme V' C V tale che per ogni vertice
u e V - V' esiste un nodo v
e V' adiacente ad u (ovvero per
cui (u, v) e E). La misura di un Insieme
Dominante è la cardinalità |V'| dell'insieme V'.
(N.B.: e = ' rovesciato).
Il problema del Minimo Insieme Dominante per G consiste nel determinare
un Insieme Dominante V' per G di cardinalità minima. Tale
problema è NP-completo.
· Sia dato un grafo G = (V, E).
· Inizializza V' = 0 (insieme vuoto) e ripeti il passo seguente
finchè ci sono nodi non dominati in G (un nodo u e
V è non dominato se u e V -
V' e nessun nodo v e V' è
adiacente ad u):
Inserisci in V' il nodo v e V
- V' che domina il massimo numero di nodi in V - V' che non
sono dominati da nodi in V'.
- Mostrare che l'algoritmo proposto non trova sempre un Insieme Dominante di cardinalità minima.