In questo esercizio si vuol analizzare l'algoritmo per trovare le componenti fortemente connesse in grafi diretti.
A tal fine si scrivano i seguenti programmi:
-
un programma per la generazione di grafi causali con un numero di nodi a scelta ed una determinata probabilità di presenza di archi tra vertici (ad esempio il programma potrebbe partire da una matrice di adiacenza contenente tutti 0 e potrebbe proseguire scorrendo gli elementi della matrice cambiando ad 1 un arco con una certa probabilità)
-
un programma per cercare le componenti fortemente connesse, implementando sia DFS che DFS-VISIT
-
Un programma che permetta di condurre esperimenti su grafi casuali con dimensione crescente e con probabilità di presenza di archi crescente.
-
Descrivere infine gli esperimenti condotti in una relazione, allegando alla stessa sia il file .pdf che il .tex e tutte le illustrazioni presenti nella relazione