[Teoria dei grafi] Grafo aciclico non orientato (Albero)

[wingman87]

La domanda è semplice: come fa un grafo non orientato con almeno un arco ad essere aciclico? Per lo meno non si può prendere per buona la definizione di aciclicità per grafi orientati anche per i non orientati. Solo che non ho trovato altre definizioni...
EDIT: ho dimenticato di aggiungere "connesso" alla definizione di albero

[alucard82]

Originariamente inviato da wingman87

La domanda è semplice: come fa un grafo non orientato con almeno un arco ad essere aciclico? Per lo meno non si può prendere per buona la definizione di aciclicità per grafi orientati anche per i non orientati. Solo che non ho trovato altre definizioni...
EDIT: ho dimenticato di aggiungere "connesso" alla definizione di albero

Mi spieghi cosa vorresti sapere?

E' ovvio che se il grafo è non orientato, aciclico e connesso esso è un albero! non riesco a capire la tua domanda. Spiegati un pò meglio.

ciao

[wingman87]

Il problema è questo: un ciclo è un cammino di lunghezza almeno 1 che inizia e termina nello stesso vertice. Ora se ho un grafo non orientato con un arco che connette A e B posso fare il seguente cammino: A->B->A e quindi ho un ciclo.
Quindi non capisco come può un grafo non orientato con almeno un arco essere aciclico... Ci dev'essere un'altra definizione di aciclicità per grafi non orientati, altrimenti non me lo spiego.

Parti da questa definizione:
Un albero è un grafo non orientato connesso e aciclico.

Questa è la definizione di aciclicità:
Un ciclo sussiste se: esiste un solo cammino che connette due vertici del grafo.

Essendo il grafo non orientato il percorso A->B->A non è un ciclo! Per definizione di "non orientato" l'arco A-B e l'arco B-A sono lo stesso arco.

Applicando la definizione di aciclicità, devi considerare ogni coppia di archi Se per almeno una coppia trovi almeno due percorsi distinti che dal primo nodo scelto vanno al secondo allora hai trovato un ciclo! Quel distinti è molto importante xD

Verificherai facilmente che nel caso da te citato non ci sono cicli.

[wingman87]

Scusa ma non ci ho capito niente...
La definizione di ciclo che hai dato non l'ho mai sentita, dove l'hai presa?

Un ciclo sussiste se: esiste un solo cammino che connette due vertici del grafo.

E comunque non mi sembra abbia molto senso...

Questa è la definizione di aciclicità:

Alla fine non l'hai scritta

Applicando la definizione di aciclicità,

Quale?

Forse è solo la tarda ora. Domani provo a risbatterci la testa. Grazie comunque

[wingman87]

Sìììììì ho capito!!! E' proprio vero che la notte porta consiglio
Ci ho rimuginato su e ora mi è chiaro cosa intendevi. Però ho ancora una domanda, quel vincolo che hai imposto sui cicli:

Un ciclo sussiste se: esiste un solo cammino che connette due vertici del grafo.

Dove l'hai preso? Non l'ho trovato da nessuna parte ma mi sembra molto importante. Questa è la definizione che ci ha dato il prof, te la linko da wikipedia perché è uguale:
LINK

[wingman87]

Up
Metto insieme tutti i dubbi in un'unica domanda:
qual è la definizione di ciclo in un grafo non orientato?
Riporto quella che si trova su wikipedia e che è anche quella delle dispense del mio prof:

In un grafo si dice ciclo di lunghezza m una catena (v0, ..., vm-1, v0); si dice ciclo semplice un ciclo (v0, ..., vm-1, v0) per il quale

∀i, k = 1, ..., m-1, (i ≠ k → vi ≠ vk)

cioè un ciclo che non passa due volte dallo stesso nodo.

E la definizione di catena:

Sia G = (V, E) un grafo orientato o non orientato: una n-upla di nodi (v0, ..., vm) si dice catena di lunghezza m tra v0 e vm se:

∀i = 1, ..., m, (vi-1, vi) ∈ E ∨ (vi, vi-1) ∈ E

Una catena (v0, ..., vm, v0) si dice ciclica. Un grafo a-ciclico può contenere catene cicliche, nel qual caso non è singolarmente connesso.

Vedo ora la parte che ho evidenziato in grassetto, che vuol dire "singolarmente connesso"? Magari è la risposta che cerco. Ma poi che senso ha? Aciclico non vuol dire senza cicli dunque? Non ci capisco più nulla

[wingman87]

Ci ho messo tanto ma alla fine ho trovato una definizione che colmasse tutti i miei dubbi:
http://www.dist.unige.it/msanguineti.../RO1SV/D11.pdf
a pagina 8:

Dato G=(V,E) non orientato si dice cammino semplice o percorso
(path) in G, P={v0,v1,...,vk} un cammino tale che tutti i nodi ed archi
che lo compongono sono distinti.

W={v0,v1,...,vk, v0} è detto cammino chiuso

Un cammino semplice chiuso è detto ciclo

C'è qualche piccola imprecisione ma il concetto è chiaro. Spero che sia utile anche ad altri

Scusa per il ritardo ma mi connetto solo sul tardi:

Questa è una definizione formale:
(per me la più intuitiva)

Un percorso di lunghezza n nel grafo G è dato da una sequenza di vertici {v0,v1,..., vn} (non necessariamente tutti distinti) e da una sequenza di archi che li collegano {(v0,v1),(v1,v2),...,(vn-1,vn)}. I vertici v0 e vn si dicono estremi del percorso.

• Un percorso con nodi tutti distinti prende il nome di cammino.
• Un cammino chiuso (v0 = vn) si chiama circuito o ciclo.

Alla fine, naturalmente, corrisponde con quella che hai trovato tu. Non ho voluto darti subito quella formale perchè secondo me può creare confusione.
Sono contento che tu abbia risolto

[wingman87]

Originariamente inviato da Stefano Cancedda

Scusa per il ritardo ma mi connetto solo sul tardi:

Questa è una definizione formale:
(per me la più intuitiva)

Un percorso di lunghezza n nel grafo G è dato da una sequenza di vertici {v0,v1,..., vn} (non necessariamente tutti distinti) e da una sequenza di archi che li collegano {(v0,v1),(v1,v2),...,(vn-1,vn)}. I vertici v0 e vn si dicono estremi del percorso.

• Un percorso con nodi tutti distinti prende il nome di cammino.
• Un cammino chiuso (v0 = vn) si chiama circuito o ciclo.

Alla fine, naturalmente, corrisponde con quella che hai trovato tu. Non ho voluto darti subito quella formale perchè secondo me può creare confusione.
Sono contento che tu abbia risolto

Però la tua definizione di ciclo non aggiunge il vincolo che il cammino non può usare due volte lo stesso arco. Cioè, questa restrizione è ovvia se il grafo è orientato e infatti questa è la stessa definizione che ho trovato a riguardo dei grafi orientati, quando poi però sono arrivato a studiare gli alberi mi è venuto il dubbio che la definizione di ciclo fosse diversa per i grafi non orientati.
Ad ogni modo grazie