Slalom

Non riesco a immaginare altra soluzionese non un procedimento a forza brutta che provi tutte le combinazioni, qualcuno può darmi qualche hint (aka suggerimenti) a riguardo? Grazie 

Vedilo come un albero

Vedilo come un albero

Degiac

Potresti essere un po' più preciso?  

È un problema tipo minum dominanting set su un albero?

È un problema tipo minum dominanting set su un albero?

riccardomereu5

Io lo vedo più come una programmazione dinamica su albero.

UPD:
Prima di tutto, considera queste due possibilità: mi trovo nel nodo G e il figlio/i del nodo è N.

1)Se ho "montato" la telecamera in G, sono obbligato a costruirla in N?
2) Se non ho montato la telecamera in G, devo costruirla per forza in N?

Comunque

 
È un problema tipo minum dominanting set su un albero?

riccardomereu5

Sì, è esattamente il problema del Dominating set, su un albero invece che un grafo generico :slight_smile: ed esiste una soluzione con programmazione dinamica.

UPD: anzi no, è il Vertex cover (il Dominating set è definito in modo leggermente diverso)