Grafo delle componenti fortemente connesse

All'ultimo esame di Algoritmi 1 sono stato rimandato poichè non avevo ben chiaro cosa fosse il grafo delle componenti fortemente connesse di un grafo G=(V,E).Fino ad oggi pensavo che questo tipo di grafo dovesse contenere forzatamente cicli e che quindi non poteva essere effettuato su di esso un ordinamento topologico.Oggi mi devo risentire, questo tipo di grafo è un grafo diretto aciclico e quindi topologicamente ordinabile.Vediamo in dettaglio la sua definizione.Componenti Fortemente ConnesseLe componenti fortemente connesse (C1, C2, ..., Cn) di un grafo orientato G=(V,E) sono sottografi di G composti da vertici mutalmente raggiungibili.Quindi, per ogni componente fortemente connessa Ci=(Vi, Ei) si ha che per ogni coppia u,v di vertici in Vi si ha un percorso u~v ed un percorso v~u in Ei.Grafo delle Componenti Fortemente ConnesseSi definisce grafo delle componenti fortemente connesse il grafo G~=(V~,E~) (di un grafo G=(V,E) ) conV~={C1, C2, ..., Cn}E~={(Ci,Cj) : i diverso da j e (x,y) in E con x in Ci e y in Cj}Ovvero un grafo che ha come vertici le componenti fortemente connesse del grafo G e come archi quegli archi che collegano un qualsiasi vertice in Ci con un qualsiasi vertice in Cj.Questo grafo è aciclico in quanto è possibile trovare un arco uscente da Ci e incidente in Cj ma non può esistere l'arco uscente da Cj e incidente in Ci perchè in tal caso ogni vertce u di Ci sarebbe mutalmente raggiungibile da ogni vertice v Cj ovvero Ci e Cj sarebbero la stessa componente fortemente connessa.Ora, essendo questo un grafo aciclico si può eseguire un algoritmo di ordinamento topologico in G~. A prestoDario