1. Dato il grafo orientato rappresentato dalla seguente matrice di adiacenza:

   

   • Indicare il grado del nodo 1
   • Indicare il numero di nodi della più grande componente fortemente connessa del grafo
   • Soluzione

2. Dato il grafo non orientato rappresentato dalle seguenti liste di adiacenza:

   

   • Indicare il grado del nodo 6
   • Indicare il numero di componenti connesse del grafo
   • Soluzione

1. Dato il seguente grafo orientato G:

   

   E il seguente algoritmo di visita in ampiezza

   

   Si consideri la visita ottenuta dalla chiamata BFS(G,7) supponendo che le liste Adj di ciascun nodo siano in ordine crescente di chiave

   • Indicare la chiave del quinto nodo da assumere il colore GRAY durante la visita
   • Indicare il valore di d[1] al termine della visita
   • Soluzione

2. Dato il seguente grafo non orientato G:

   

   E il seguente algoritmo di visita in profondità

   

   Si consideri la visita ottenuta dalla chiamata DFS(G,1) supponendo che le liste Adj di ciascun nodo siano in ordine crescente di chiave.

   • Indicare la chiave del quinto nodo da assumere il colore BLACK durante la visita
   • Indicare il valore di d[3] al termine della visita
   • Soluzione

1. Dato il seguente grafo non orientato G avente un unico albero minimo ricoprente (MST):

   

   Si consideri l’applicazione dell’algoritmo di Kruskal a G

   

   • Indicare il peso del secondo arco scartato dall’algoritmo (Il secondo arco (u,v) per cui la condizione a riga 5 non è verificata)
   • Indicare il peso dell’ultimo arco aggiunto a T dall’algoritmo
   • Soluzione

2. Dato il seguente grafo non orientato G avente un unico albero minimo ricoprente (MST):

   

   Si consideri l’applicazione dell’algoritmo di Prim a G con nodo di partenza r = b

   

   • Indicare il primo valore diverso da $\infin$ assegnato a key[d] nel corso dell’algoritmo
   • Indicare l’ultimo nodo estratto dalla coda Q
   • Soluzione

Algoritmo di Dijkstra

Dato il seguente grafo non orientato G.

Si consideri l’applicazione dell’algoritmo di Dijkstra a G con nodo sorgente s = a

Riempire la tabella sottostante con i valori di $d$ e $\pi$ per ogni nodo del grafo nel momento in cui il nodo $b$ è estratto dalla coda Q (Riga 7). Usare 999 per indicare $\infin$

• Soluzione