Grafi

In Informatica, come per le tabelle e gli alberi, esistono diversi metodi per descrivere dichiarazione e contenuto di un grafo stradale ….leggi tutto

es. 5.1  Dato il grafo corrispondente alla seguente dichiarazione

arco(to,mi,140)
arco(mi,pd,180)
arco(mi,ge,100)
arco(to,ge,120)
arco(ge,pc,170)
arco(ge,fi,230)
arco(pd,bo,150)
arco(pc,bo,160)
arco(bo,fi,90)
arco(bo,rn,110)
arco(rn,rsm,20)
arco(rn,an,100)
arco(an,pe,140)
arco(fi,rm,230)
arco(rm,pe,170)

Disegnare il grafo e rispondere alle seguenti domande, riportando le risposte nella tabella

  1. Calcolare la distanza minima fra i nodi rsm e rm.
  2. Trovare la distanza dei nodi, estremi esclusi, del percorso più corto fra ge e an.
  3. Trovare la lista del percorso più lungo fra i nodi to e rn, che non contenga nodi ripetuti.
  4. Quanti percorsi disgiunti (cioè senza nodi intermedi comuni) esistono fra rsm e rm?
  5. Quanti percorsi disgiunti esistono fra rn e rm?
1 2 3 4 5
         

 es 5.2  Dato il grafo corrispondente alla seguente dichiarazione

arco(to,mi,140) arco(mi,pd,180) arco(mi,ge,100)
arco(to,ge,120) arco(mi,pc,65) arco(ge,pc,170)
arco(ge,fi,230) arco(pd,bo,150) arco(pc,bo,160)
arco(bo,fi,90) arco(bo,rn,110) arco(rn,rsm,20)
arco(rn,an,100) arco(an,pe,120) arco(fi,rm,230)
arco(rm,pe,170)    

 Il signor Marius Rossinis vuole fare un viaggio in auto; ha a disposizione 60 euro e sa che dovrà spendere 2 euro per ogni 12 km percorsi (complessivamente per pedaggi e per combustibile)

  1. Qual è la città x1 che può raggiungere, fra quelle descritte nel grafo, partendo da Roma?
  2. Qual è la lista delle targhe automobilistiche che descrivono il percorso da Roma a x1?
  3. Qual è la città x2 più lontana che può raggiungere, fra quelle descritte nel grafo, partendo da Torino?
  4. Qual è la lista delle targhe automobilistiche che descrivono il percorso da Torino a x2?
  5. Qual è la città x3 più lontana che può raggiungere, fra quelle descritte nel grafo, partendo da San Marino (rsm)?
  6. Qual è la lista delle targhe automobilistiche che descrivono il percorso da San Marino a x3?
 1 2 3 4 5  6
 bo  [rm,fi,bo]  ……..    [………] ……..   [………]