testare se un grafo è un albero

[f_brizio_f]

Ciao a tutti ragazzi, non capisco come svolgere questo esercizio base sui grafi, potreste darmi una mano?
anche a capire meglio come funzionano, che sono un po' in alto mare.
Esercizio.
Dato un grafo G = (V, E) non orientato, progettare un algoritmo per testare se il
grafo `e un albero. Dare lo pseudo-codice e discutere la complessità.

[vict85]

Un tuo tentativo?

Che interfaccia usi per l'oggetto grafo? Per esempio, hai accesso diretto all'insieme degli archi oppure accedi agli archi tramite i vertici? Detto questo un albero (i) non ha cicli ed (ii) è connesso. Inoltre (iii) \(\lvert V \rvert = \lvert E \rvert + 1\) (questo si può dimostrare usando gli altri altri due). Su wiki trovi per esempio che la proprietà (iii) insieme ad una qualsiasi tra (i) e (ii) è sufficiente per dimostrare che qualcosa è un grafo. Sapresti trovare un algoritmo per dimostrare che un grafo è connesso? E per l'aciclicità?

[apatriarca]

Come piccolo suggerimento, prova a considerare un nodo a caso e di fare una visita del tuo grado. Per essere un albero deve rispettare due proprietà: è connesso e non ha cicli (c'è un solo percorso che connette ogni due vertici). In che modo queste due proprietà si trasmettono in quello che osservi visitando il grafo?