TAG
MENU
« End of Session | Erasmus Incoming » |
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
|
CERCA IN QUESTO BLOG
ULTIMI COMMENTI
Inviato da: dariospy
il 03/04/2009 alle 15:33
Inviato da: Giorgio
il 03/04/2009 alle 10:42
Inviato da: Smò
il 26/03/2009 alle 23:26