[ALGORITMI] Dubbio ordinamento topologico grafi

[ciccioalex]

salve,
ho un dubbio relativo alla seguente domanda:
-l'ordinamento topologico di un grafo orientato è unico se:
a)il grafo è aciclico
b)se il grafo non contiene archi
c)se il grafo contiene un arco per ogni coppia di nodi
d)se valgono entrambe le ipotesi a e c

Ora:
esempio di grafo aciclico:
a --> b--->c d
ordinamento topologico:
1) a,b,c,d
2)d,a,b,c

esempio di grafo senza archi:
a b c d
ordinamento topologico:
1) a, b, c, d
2)d, c, b, a

esempio di grafo con un arco per ogni coppia di vertici (anche aciclico):
a-->b--> c <---d<---e
ordinamento topologico:
1)a,b,e,d,c
2)e,d,a,b,c

Sbaglio qualcosa? Grazie

[apatriarca]

L'ultimo esempio è sbagliato.. Dice che ci deve essere un arco per ogni coppia di vertici, ma non hai archi tra 'a' ed 'e' o tra 'a' e 'd' o tra 'b' e 'd' o tra 'b' ed 'e'. Se aggiungiamo queste relazioni, per esempio a -> d, d -> b, a -> e, e -> b, a -> c ed e->c, otteniamo un ordinamento topologico unico: a e d b c.

[ciccioalex]

ok,
quindi la risposta esatta è la d? (altrimenti potrebbe esistere un cappio)

[apatriarca]

Sì.. è la d.

[ciccioalex]

Chiarissimo, grazie