[Algoritmi] Componenti connesse che sono alberi? [GRAFO]

[Giova411]

Buongiornissimo,
Scrivere un algoritmo che, dato un grafo non orientato, conti il numero delle sue componenti connesse che sono anche alberi. Discuterne la complessità.

Non ho capito proprio il testo!
Cioé mi chiede di contare una sorta di FORESTA interna al grafo?
Poi si riferisce, implicitamente, ad alberi minimi di copertura?
Devo verificare, quindi, la presenza di cicli nelle componenti connesse?


grazie

[onlyReferee]

Buongiornissimo,
[...]

Ciao Giova411

[...]
Non ho capito proprio il testo!
[...]

Nessun problema...

[...]
Cioé mi chiede di contare una sorta di FORESTA interna al grafo?
[...]

Sì, se con foresta intendiamo un insieme di alberi (liberi) bisogna contare gli elementi che compongono tale foresta.

[...]
Poi si riferisce, implicitamente, ad alberi minimi di copertura?
[...]

No perché per determinare un albero di copertura minimo dobbiamo avere un grafo pesato e nella consegna è specificato che abbiamo in input un grafo non orientato senza dire nulla riguardo ai pesi. A questo scopo (determinare gli alberi di copertura minimi) come sai abbiamo già gli algoritmi di Kruskal e Prim.

[...]
Devo verificare, quindi, la presenza di cicli nelle componenti connesse?
[...]

Esatto. Questo come sappiamo vuol dire in pratica verificare se esistono vertici per cui è presente un cammino che inizi e termini in sé stesso (poiché siamo un grafo non orientato sappiamo già che non ci sono cappi).

[...]
grazie

Di nulla, a te .

[Giova411]

Forse ho un po' di confusione ancora...
Ma non capisco bene il discorso sui cicli allora.
Un albero può essere formato anche da un solo nodo che potrebbe essere una componente connessa a se nel grafo.
Non conto anche queste situazioni? Perché solo quando trovo un ciclo aumento il conteggio di uno?

[onlyReferee]

:D
Forse ho un po' di confusione ancora...
Ma non capisco bene il discorso sui cicli allora.
Un albero può essere formato anche da un solo nodo che potrebbe essere una componente connessa a se nel grafo. Non conto anche queste situazioni?
[...]

Sì, certo che le conti, perché no Un solo nodo è un albero in quanto non ci sono cicli (banale) ed è una componente connessa.

[...]
Perché solo quando trovo un ciclo aumento il conteggio di uno?

Se riusciamo ad individuare un ciclo in una componente connessa caso mai non conteggiamo la stessa. Prima pertanto bisogna individuare le componenti connesse e poi si vede se è o meno presente un ciclo all'interno di ciascuna di esse. Supponiamo di avere un grafo con $n$ vertici e $k$ archi. Allora (se ti può aiutare):

• Hint 1: se $k < n - 1$ allora avrò sicuramente almeno due componenti connesse;
• Hint 2: se $k > n - 1$ allora avrò sicuramente un ciclo.

PS: premetto che sono andato un po' a memoria ed un po' rifacendomi un esempio su carta per ricavare le relazioni precedenti senza riprendere in mano gli appunti di Analisi e Progetti di Algoritmi (non dovrei aver detto fandonie, almeno spero ).

[Giova411]

Only Prof Buondì!
Cavoli sono duro di capoccia lo sai!

Allora tu dici:
- contiamo le componenti connesse senza cicli (abbiamo una foresta di alberi staccati interni ad un grafo disconnesso)
- contiamo le componenti connesse con cicli (in questo caso, non essendo orientato abbiamo archi con andata+ritorno)

Quindi, ad un ignorantone come me, per risolvere l'esercizio gli basterebbe contare le componenti connesse? Contare i cicli sarebbe superfluo? Difatti rileggendo: <<...contare il numero delle componenti connesse che sono anche alberi...>>

Poi vedendo qui le cose non mi tornano ancora: http://wikiricop.diiga.univpm.it/mediaw ... i_notevoli
Se leggo nella sezione << 5) alberi >> trovo:
<< 1) Foresta: Si definisce foresta, o albero aciclico, un grafo non orientato che non contiene cicli>>

Poi pensavo: i cicli nel grafo li voglio contare una volta quando posso partire da un vertice qualsiasi e ritrovarmi in esso con "una passata" così da poter dire che ho un albero. Questo "pensiero" è corretto

La definizione seguente <<..in teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino. Grafo non orientato, connesso e privo di cicli! >>
Allora perché contiamo i cicli?

[onlyReferee]

Ciao Giova411
Cerco un attimo di farti venir fuori da questa piccola confusione.

[...]
Quindi, ad un ignorantone come me, per risolvere l'esercizio gli basterebbe contare le componenti connesse? Contare i cicli sarebbe superfluo? Difatti rileggendo: <<...contare il numero delle componenti connesse che sono anche alberi...>>
[...]
La definizione seguente <<..in teoria dei grafi un albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino. Grafo non orientato, connesso e privo di cicli! >>
Allora perché contiamo i cicli?

Io nel mio post precedente non ho affermato che bisogna contare i cicli ma che basta sapere se questi ci sono o meno in ciascuna componente connessa che andiamo ad "analizzare" (dopo averle individuate chiaramente). L'hint 2 che ho suggerito ci dice infatti che c'è almeno un ciclo nel grafo ma non so (e nel nostro caso ci interessa) se gli stessi sono $1, 2$ o $100$.
Di fatto comunque conoscendo il numero totale di componenti connesse del grafo (sia con che senza cicli all'interno delle stesse) ed il numero di componenti connesse con cicli (ergo quelle che non sono alberi), il numero di quelle che sono alberi lo si ricava facilmente per differenza, no

[Giova411]

Sono io nel caos

Allora riprendo la definizione di Foresta:
Si definisce foresta un grafo non orientato nel quale due vertici qualsiasi sono connessi al più da un cammino (grafo non orientato e privo di cicli). Una foresta risulta costituita da un'unione disgiunta di alberi (e questa proprietà giustifica il suo nome); questi alberi costituiscono le sue componenti connesse massimali.

Cioé ogni ciclo nel grafo (non orientato) corrisponde ad un albero? E non conto un arco due volte? Ci sono??

Metto una SOLUZIONE 1:

[onlyReferee]

[...]
Cioé ogni ciclo nel grafo (non orientato) corrisponde ad un albero? E non conto un arco due volte? Ci sono??
[...]

No... Un albero è un grafo aciclico e connesso per definizione. Questa è l'unica relazione che c'è tra cicli ed alberi, altre (che io sappia) non ve ne sono.
Se il grafo è non orientato per noi $(u, v)$ e $(v, u)$ con $u, v \in V$ rappresentano il medesimo arco.

[Giova411]

Prof non ti incavolare
Allora conto le componenti connesse e se non ci sono cicli è fatta?!

Il codice è esaustivo per il suddetto problema?


Grazie per la pazienza... Spero di non mandare nel caos pure te

[onlyReferee]

Nessuno si è incavolato, tranquillo (in un forum è anche più difficile riuscire a percepire quando questo succede). Ho solo spiegato meglio un concetto che non era ancora chiaro...
Sì, il codice allegato mi sembra esaustivo.
Nessuno è andato nel caos, figurati .