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

Thompson wrote:

> 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..

Spesso lo si implica ma, a rigore, quello che non ha nodi ripetuti si
dovrebbe chiamare /cammino semplice/; invece un cammino (path) in
generale, può avere nodi ripetuti:
http://en.wikipedia.org/wiki/Path_%28graph_theory%29

> Prima dicevo che, se i pesi degli archi sono tutti positivi, allora un
> percorso MINIMO da un nodo ad un'altro è perforza aciclico.

Infatti, ma questo deriva dalla *minimizzazione* del cammino tra due
nodi, non dalla definizione di cammino (path).

> Non ho letto il Bollobas, ma in letteratura di solito un cammino in
> inglese viene scritto "acycle-path".

Scritto così significherebbe più o meno "pista ciclabile" :-)
Semmai si parla di /acyclic-path/.

Ciao.
[ Auf dieses Posting antworten ]