[Grafi] Radice di una componente fortemente connessa

[Andrew Ryan]

Dato un grafo diretto G,sapendo che le componenti fortemente connesso partizionano il grafo,come riconosco una radice di una componente fortemente connessa? Devo per forza visitare un sottoalbero di un nodo U qualsiasi utilizzando la DFS? E allora in questo caso l'ordine di visita non mi darebbe sempre quel nodo U come primo nodo visitato? Per sapere se U è una radice della componente fortemente connessa mi basta verificare che da U si raggiungano tutti i nodi del suo sottoalbero?

[apatriarca]

Non esiste alcuna radice di una componente fortemente connessa. Non si tratta di un albero.

[Andrew Ryan]

"apatriarca":Non esiste alcuna radice di una componente fortemente connessa. Non si tratta di un albero.

mi spiace contraddirti ma sul fatto che esistano non ho dubbi,ho davanti a me delle dispense del mio professore che ne parlano (oltre averle viste ieri a lezione),se ne parla anche qui su wikipedia: http://it.wikipedia.org/wiki/Algoritmo_ ... e_connesse

il problema è che non ho capito benissimo come faccio a riconoscerle...

[apatriarca]

Le "radici" di cui si parla nell'articolo (e probabilmente nella tua lezione) non sono univocamente determinate dal grafo, ma dipendono anche dall'algoritmo usato per visitare i nodi a dalla scelta dei nodi di partenza. È in questo senso che dico che non esiste alcuna radice univoca per una componente fortemente connessa. Dipende semplicemente da quale nodo della componente fortemente connessa viene visitato prima nell'algoritmo.

[Andrew Ryan]

"apatriarca":Le "radici" di cui si parla nell'articolo (e probabilmente nella tua lezione) non sono univocamente determinate dal grafo, ma dipendono anche dall'algoritmo usato per visitare i nodi a dalla scelta dei nodi di partenza. È in questo senso che dico che non esiste alcuna radice univoca per una componente fortemente connessa. Dipende semplicemente da quale nodo della componente fortemente connessa viene visitato prima nell'algoritmo.

Per visitato prima intendi il nodo di una delle componenti fortemente connesse del grafo che viene visitato prima dalla DFS? Quindi il fatto che da quel nodo si possano raggiungere tutti gli altri della sua componente non c'entra niente? oppure si?

[apatriarca]

Ogni nodo è raggiungibile da chiunque altro in una componente fortemente connessa. È la definizione stessa di componente fortemente connessa..

[Andrew Ryan]

"apatriarca":Ogni nodo è raggiungibile da chiunque altro in una componente fortemente connessa. È la definizione stessa di componente fortemente connessa..

appunto,è per questo che mi chiedo come faccio a determinare quale sia la radice della componente L'ordine chi lo decide,la DFS? e poi in base all'albero di visita ottenuto si determina quale sia la radice? oppure se ho un grafo davanti a me posso decidere quale sia la radice solamente analizzando il grafo?

[apatriarca]

Come ti ho già detto, la radice dipende dall'ordine di visita dei nodi nella DFS.