[Algoritmi] Componenti connesse che sono alberi? [GRAFO]
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
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
Risposte
"Giova411":
Buongiornissimo,
[...]
Ciao Giova411
"Giova411":
[...]
Non ho capito proprio il testo!
[...]
Nessun problema...
"Giova411":
[...]
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.
"Giova411":
[...]
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.
"Giova411":
[...]
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).
"Giova411":
[...]
grazie
Di nulla, a te
.
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?
"Giova411":
: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."Giova411":
[...]
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):
[*:ynonlvvq]Hint 1: se $k < n - 1$ allora avrò sicuramente almeno due componenti connesse;[/*:m:ynonlvvq]
[*:ynonlvvq]Hint 2: se $k > n - 1$ allora avrò sicuramente un ciclo.[/*:m:ynonlvvq][/list:u:ynonlvvq]
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
).
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?
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?
Ciao Giova411
Cerco un attimo di farti venir fuori da questa piccola confusione.
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
Cerco un attimo di farti venir fuori da questa piccola confusione.
"Giova411":
[...]
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
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:
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:
"Giova411":
[...]
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.
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
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
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.
Sì, il codice allegato mi sembra esaustivo.
Nessuno è andato nel caos, figurati
.
Grandissimo!! Grazie per la pazienza davvero!
No, in realtà, ero io nervoso con me stesso
Mi sono bloccato con le definizioni quando basta prendere "carta e penna" e ragionarci con calma e nel "vecchio stile"
Forse ho trovato un'altra soluzione che metto per tutti coloro i quali, nel futuro, avranno questi quesiti.
Soluzione 2 che si basa su Discovery Time e Finish Time e contiamo proprio la grandezza della FORESTA interna al grafo.
La funzione "ciclico" ci dice se abbiamo cicli.
Costo totale efficente O(m+n) come una visita semplice
No, in realtà, ero io nervoso con me stesso
Mi sono bloccato con le definizioni quando basta prendere "carta e penna" e ragionarci con calma e nel "vecchio stile"
Forse ho trovato un'altra soluzione che metto per tutti coloro i quali, nel futuro, avranno questi quesiti.
Soluzione 2 che si basa su Discovery Time e Finish Time e contiamo proprio la grandezza della FORESTA interna al grafo.
La funzione "ciclico" ci dice se abbiamo cicli.
Costo totale efficente O(m+n) come una visita semplice
Only concedimi un'ultima domanda.
Dal grafo della seguente pagina:
[url]http://it.wikipedia.org/wiki/Albero_(grafo)#mediaviewer/File:Graph_theory_tree.svg[/url]
Operando col codice che, anche tu, ritieni esaustivo (ossia la prima versione) avrò come risultato il numero $1$? Giusto?
L'analisi la fa in una sola chiamata a countTreesDFS che, a sua volta, in una sola "passata in profondità" restituisce TRUE, cioé che è aciclico (difatti vedasi figura d'esempio nel link)
Se, all'immagine, aggiungiamo un NODO SOLITARIO ad esempio NODO (8) senza alcun arco, quindi disconnesso al resto mostrato in figura, abbiamo 2 chiamate a countTreesDFS e risultato pari a $2$
"Detto a voce" ho capito bene?
Dal grafo della seguente pagina:
[url]http://it.wikipedia.org/wiki/Albero_(grafo)#mediaviewer/File:Graph_theory_tree.svg[/url]
Operando col codice che, anche tu, ritieni esaustivo (ossia la prima versione) avrò come risultato il numero $1$? Giusto?
L'analisi la fa in una sola chiamata a countTreesDFS che, a sua volta, in una sola "passata in profondità" restituisce TRUE, cioé che è aciclico (difatti vedasi figura d'esempio nel link)
Se, all'immagine, aggiungiamo un NODO SOLITARIO ad esempio NODO (8) senza alcun arco, quindi disconnesso al resto mostrato in figura, abbiamo 2 chiamate a countTreesDFS e risultato pari a $2$
"Detto a voce" ho capito bene?
Riguardo al primo grafo (quello linkato in figura): sì, restituisce $1$ e la funzione countTreesDFS viene eseguita una volta soltanto. A livello di complessità infatti non bisogna farsi ingannare dal for each all'interno di countTrees: l'if presente nello stesso fallirà banalmente per tutti i vertici successivi al primo che viene passato a countTreesDFS in quanto gli stessi risulteranno difatti già visitati.
Riguardo al secondo grafo da te proposto (se aggiungi un nodo con valore $8$ senza collegamenti, ergo $8$ è vertice isolato) e tenendo conto della considerazione precedente è corretto affermare che countTreesDFS verrà eseguita due volte.
In conclusione hai capito giusto
Riguardo al secondo grafo da te proposto (se aggiungi un nodo con valore $8$ senza collegamenti, ergo $8$ è vertice isolato) e tenendo conto della considerazione precedente è corretto affermare che countTreesDFS verrà eseguita due volte.
In conclusione hai capito giusto
"onlyReferee":
A livello di complessità infatti non bisogna farsi ingannare dal for each all'interno di countTrees: l'if presente nello stesso fallirà banalmente per tutti i vertici successivi al primo che viene passato a countTreesDFS in quanto gli stessi risulteranno difatti già visitati.
Sì infatti mi ingannano ste cose
"onlyReferee":
In conclusione hai capito giusto
Finalmente puoi dirlo forte, non mi offendo!
Grazie PROF.!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo