Grafi – E3

di

L’ufficio tecnico di un piccolo comune deve scegliere dove piazzare dei nuovi lampioni.

Il paese di cui si parla può essere pensato come un insieme di piazzette collegate da strade, descritte dal seguente grafo (dove i nodi sono le piazze e gli archi sono le strade):

  • arco(n1,n2)
  • arco(n2,n3)
  • arco(n3,n1)
  • arco(n4,n1)
  • arco(n4,n2)
  • arco(n4,n5)

Ogni lampione illumina la piazza in cui è collocato, le strade da essa uscenti, e le piazze direttamente collegate alla piazza in cui si trova il lampione.

Trovare:

  1. il numero minimo di lampioni che consente di illuminare tutto il paese;
  2. la lista delle piazze (cioè dei nodi del grafo) su cui collocare tali lampioni, in modo che nessuna piazza sia illuminata da due lampioni.

N.B. la lista deve avere gli elementi in ordine crescente (n1<n2< …<n5).

DISCUSSIONE

Il grafo corrispondente

Se si accende un unico lampione

  • [n1] illumina [n1,n2,n3,n4,n5]
  • [n2] illumina [n1,n2,n3,n4,n5]
  • [n3] illumina [n1,n2,n3,n4,n5]
  • [n4] illumina [n1,n2,n3,n4,n5]
  • [n5] illumina [n1,n2,n3,n4,n5]

Se si accendono 2 lampioni

  • [n1,n2] illuminano [n1,n2,n3,n4,n5]
  • [n1,n3] illuminano [n1,n2,n3,n4,n5]
  • [n1,n4] illuminano [n1,n2,n3,n4,n5], tutte le piazze sono illuminate
  • [n1,n5] illuminano [n1,n2,n3,n4,n5], tutte le piazze sono illuminate
  • [n2,n3] illuminano [n1,n2,n3,n4,n5]
  • [n2,n4] illuminano [n1,n2,n3,n4,n5], tutte le piazze sono illuminate
  • [n2,n5] illuminano [n1,n2,n3,n4,n5], tutte le piazze sono illuminate
  • [n3,n4] illuminano [n1,n2,n3,n4,n5], tutte le piazze sono illuminate
  • [n3,n5] illuminano [n1,n2,n3,n4,n5], tutte le piazze sono illuminate da un unico lampione
  • [n4,n5] illuminano [n1,n2,n3,n4,n5]

Risposte

  1. MIN=2
  2. L=[n3,n5]