-
1.Dato un grafo orientato, calcolare il grado uscente e il grado entrante. Ripetere l’esercizio sia usando una rappresentazione a matrice di adiacenza, che con liste di adiacenza.
-
2.Dato un grafo orientato, stabilire se esiste un nodo pozzo. Si definisce nodo pozzo un nodo verso il quale tutti gli altri convergono, ma dal quale non ci si può muovere.Se esso esiste, modificare opportunamente il grafo in modo da non avere più un nodo pozzo.Ripetere l’esercizio sia usando una rappresentazione a matrice di adiacenza, che a liste di adiacenza.
-
3.Dati due grafi orientati pesati rappresentati con liste di adiacenza G e H, scrivere una funzione che controlli se H è un sottografo-con-pesi-multipli di G: ovvero, H è un sottografo di G e ogni suo arco ha un peso che è multiplo rispetto al peso del corrispondente arco in G.
-
4.Dato un grafo G orientato rappresentato con liste di adiacenza, scrivere una funzione che verifichi se ci siano cicli nel grafo e,in casone esista uno, eliminil’arco che lo crea.