Qui il Titolo

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 Connesse

Le 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 Connesse

Si definisce grafo delle componenti fortemente connesse il grafo G~=(V~,E~) (di un grafo G=(V,E) ) con

V~={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 presto

Dario