Re: vi offro occasione di dimostrare la vostra cultura sulla teoria dei grafi :-

Adam Atkinson ha scritto:

> On 11 Mag, 10:19, u...@cc.it (Thompson) wrote:
> > > > Faccio sommessamente notare che Beccoblu ha scritto cammino minimo.
> > > E "cammino" esclude il riutilizzo dei nodi? (in inglese un
"path" non
> > > puo' avere nodi ripetuti,
> > > un "walk" si'. Almeno secondo la mia copia di Bollobas)
> >
> > Esattamente. Se i pesi degli archi sono tutti positivi, un percorso daun
> > nodo ad un'altro sarà perforza aciclico, dunque un cammino.

> Non seguo. Un "cammino" non ha nodi ripetuti per definizione?

Si, un cammino non ha nodi ripetuti, mentre un percorso si..
Prima dicevo che, se i pesi degli archi sono tutti positivi, allora un
percorso MINIMO da un nodo ad un'altro è perforza aciclico.
Non ho letto il Bollobas, ma in letteratura di solito un cammino in
inglese viene scritto "acycle-path".

> Se abbiamo uno spanning tree fatto da archi di lunghezza 1, e tutti
> gli altri archi hanno
> lunghezza 10^9, se fosse permesso riutilizzerei gli archi dello
> spanning tree per andare
> dappertutto.

Questo è un caso estermo, ma in generale l'albero ricoprente, radicato in
s, non è equivalente a quello dei cammini minimi, sempre radicato in s.
Sono due problemi diversi.

--

questo articolo e` stato inviato via web dal servizio gratuito
http://www.newsland.it/news segnala gli abusi ad abuse@newsland.it

[ Auf dieses Posting antworten ]

Antworten

Adam Atkinson (11.05.2008 12:00)

Mister Plop (11.05.2008 16:11)