Grafi – E1

di

È dato un grafo descritto dal seguente elenco di archi:

  • arco(n1,n2,2)
  • arco(n2,n3,2)
  • arco(n3,n1,5)
  • arco(n4,n1,1)
  • arco(n4,n2,4)
  • arco(n4,n5,3)

Disegnare il grafo e trovare:

  1. la lista L1 del percorso più breve tra n5 e n3 e calcolarne la lunghezza K1;
  2. la lista L2 del percorso più lungo (senza passare più volte per uno stesso nodo) tra n5 e n3 e calcolarne la lunghezza K2.

DISCUSSIONE

Il grafo corrispondente

Osserva

  1. [n5,n4,n2,n3]=9
  2. [n5,n4,n2,n1,n3]=14
  3. [n5,n4,n1,n3]=9
  4. [n5,n4,n1,n2,n3]=8

Risposte

  1. Il percorso più breve tra n5 e n3:
    • L4=[n5,n4,n1,n2,n3]
    • K4=8
  2. Il percorso più lungo tra n5 e n3:
    • L2=[n5,n4,n2,n1,n3]
    • K2=14