[C] verificare se un grafo è connesso

[MrX87]

Ciao a tutti, avevo un problema relativo ai grafi, in particolare devo implementare un algoritmo che verifichi se un grafo non orientato sia connesso o meno! questo teoricamente vuol dire che da ogni vertice è possibile raggiungere tutti gli altri vertici! di conseguenza, se si verifica questo è anche vero che risulterebbe un grafo fortemente connesso! giusto? poichè da ogni vertice puoi andare un qualsiasi altro vertice e quindi ritornarci! però in tutto questo mi sorge un dubbio...che senso ha chiedere si implementare un algoritmo che verifichi che un grafo non orientato è connesso?!? cioè, se non è orientato, è ovvio che sia connesso!!!!
chiedo venia se sto dicendo cavolate, ma è un dubbio che mi devo cacciare!
comunque se ci fosse qualcuno un pò più esperto, lo ringrazio molto se riesce a darmi una mano!
grazie

[MrX87]

possibile che non c'è nessuno che sappia qualcosina sui grafi?

[kosmael]

Ciao...
Penso che sia tardino per darti l'aiuto, cmq si tratta della teoria dei grafi euleriani...
Implementare questo tipo di algoritmo ha senso dato, praticamente è come avere diversi nodi (immaginali come città) con divesi archi (come vie e strade) non orientati (vuoldire che non ci sono sensi unici ma solo doppi sensi :P ).
Spero che abbia colto l'analogia.

Ciauz

[Stoicenko]

in particolare devo implementare un algoritmo che verifichi se un grafo non orientato sia connesso o meno! questo teoricamente vuol dire che da ogni vertice è possibile raggiungere tutti gli altri vertici! di conseguenza, se si verifica questo è anche vero che risulterebbe un grafo fortemente connesso! giusto?

sbagliato, vuol diure che da un nodo puoi raggiungere qualsiasi altro nodo passando però per un qualsiasi altro nodo 8quindi non serve che sia connesso direttamente ma che ci sia un circuito come diceva kosmael)

cioè, se non è orientato, è ovvio che sia connesso!!!!

sbagliato ancora.. le due cosa non hanno nessun legame

[MrX87]

Citazione:
in particolare devo implementare un algoritmo che verifichi se un grafo non orientato sia connesso o meno! questo teoricamente vuol dire che da ogni vertice è possibile raggiungere tutti gli altri vertici! di conseguenza, se si verifica questo è anche vero che risulterebbe un grafo fortemente connesso! giusto?


sbagliato, vuol diure che da un nodo puoi raggiungere qualsiasi altro nodo passando però per un qualsiasi altro nodo 8quindi non serve che sia connesso direttamente ma che ci sia un circuito come diceva kosmael)

si ma allora la definizione che c'è su wikipedia come la devo interpretare???

da wikipedia:
Grafo connesso
Un grafo si dice connesso se per ogni coppia di nodi (v,w) esiste un percorso che li unisce.

a quanto dice qua, basta verificare che presi 2 nodi del grafo, essi sono collegati...e quindi se il grafo è connesso...direi che è ovvio che sono collegati!!!

[Stoicenko]

no.. sbagli a interpretare..

da wikipedia: Grafo connesso Un grafo si dice connesso se per ogni coppia di nodi (v,w) esiste un percorso che li unisce.

Parla di percorso non di connessione diretta.. fa attenzione

Un percorso è un insieme di nodi connessi..

Ricapitolando un grafo è connesso se per ogno coppia di nodi (n1,n2) esiste un percorso (insieme di nodi) che parte da n1 e va a n2

Il punto è che tu dicevi

questo teoricamente vuol dire che da ogni vertice è possibile raggiungere tutti gli altri vertici! di conseguenza, se si verifica questo è anche vero che risulterebbe un grafo fortemente connesso

e questo è errato..

[MrX87]

Ricapitolando un grafo è connesso se per ogno coppia di nodi (n1,n2) esiste un percorso (insieme di nodi) che parte da n1 e va a n2

okay allora iniziamo a capirci...quindi un grafo orientato è sempre connesso...se dati due nodi n1 e n2 esiste un percorso( insieme di nod) che parte da n1 va a n2 attraversando più di un nodo!

mentre è sbagliato dire che è fortemente connesso!!

[Stoicenko]

diciamo che è esatto tranne il fatto che non centra se è orientato o no..

il fatto che sia orientato presuppone che il percorso rispetti l'orientamento

che parte da n1 va a n2 attraversando più di un nodo!

anche nessun nodo se sono collegati direttamente

[xela86]

l'essere fortemente connesso nasce nel caso in cui il grafo sia orientato

[MrX87]

l'essere fortemente connesso nasce nel caso in cui il grafo sia orientato

eh se il grafo non è orientato?