Il mitico ritorno del commesso viaggiatore

[Anér]

Un commesso viaggiatore deve andare nelle n città di un regno incantato a svolgere i propri affari; il primo giorno viene catapultato in una città a caso, dopo di che dovrà visitare ogni giorno una città diversa, così l'n-esimo giorno visiterà l'ultima città e il giorno dopo tornerà nella città di partenza per riessere rapito dagli alieni che lo avevano catapultato il primo giorno.

Di giorno deve svolgere i propri affari, per cui di notte deve spostarsi da una città all'altra. Esiste un servizio ferroviario gratuito che collega ogni coppia di città, tuttavia esso opera solo in un senso (ovvero se si può andare da A a B non si può andare da B ad A); esiste anche una linea aerea che collega in entrambi i sensi tutte le coppie di città, ma questa è a pagamento. Sapendo che il commesso viaggiatore non ha preferenze sull'ordine in cui deve visitare le città, quante volte al massimo dovrà prendere l'aereo?

[Tibor Gallai]

Vedi anche:
viewtopic.php?t=12361

[didudo]

non capisco.lui può benissimo farsi tutti i viaggi gratis!!vuoi sapere quanti può farne al massimo se fosse un masochista che ama spendere i soldi della ditta?

[julio14]

No, non può farli tutti gratis, perché i treni viaggiano a senso unico. Se hai due città A e B, ad esempio, e il treno va solo da A a B, se viene catapultato in B sarà costretto a prendere l'aereo. Comunque, il problema linkato da Tibor (che non ha ancora dimostrazione qua sul forum) è un forte aiuto, diciamo che è il primo passo. Fatto quello, il secondo passo è molto più facile.

[Tibor Gallai]

A quanto ne so, il problema di Anér (teorema di Rédei) è una semplificazione di quell'altro che ho linkato (teorema di Camion, poi perfezionato da Moon). Usare l'altro per dimostrare questo è come fare le cose al contrario, IMHO.
Anche storicamente i 2 teoremi sono stati scoperti nell'ordine inverso.

[julio14]

Uh, si forse si. È che, conoscendo già l'altro, questo mi sembrava semplicemente una conseguenza. In effetti questo vuol dire che il primo è un risultato più forte e difficile, ma direi che sto portando avanti una questione abbastanza futile.

[Tibor Gallai]

Del teorema di Rédei (ogni torneo ha un cammino Hamiltoniano) esiste una dimostrazione in 1 riga. L'altro di Camion-Moon è abbastanza più complicato.

[dario2994]

Scusate ma parlo da ignorante completo di teoria dei grafi et similia...
Ma quando dite Torneo che intendete?

[Tibor Gallai]

Un grafo orientato in cui ogni coppia di nodi è collegata da un arco.

[julio14]

Perché Rédei non basta per fare 1 aereo? Premetto che lo sento stasera per la prima volta, e ho appena visto su wiki cos'è un cammino Hamiltoniano, ma al commesso non basta andare in fondo al cammino e poi volare all'inizio?

[Tibor Gallai]

Sì, mi stavo accorgendo di questo un attimo fa, ho editato.

[julio14]

Che tempismo. Comunque, dopo questa breve lezione di teoria dei grafi, posso dire di essere d'accordo con la tua asserzione iniziale. (soprattutto se esiste una dimostrazione di una riga)

[Anér]

I. su n, con n$ \exists v_1\rightarrow\cdots\rightarrow v_n $, se $ v_i\rightarrow v_{n+1} \forall i \Rightarrow v_1\rightarrow\cdots v_{n+1} $, altrimenti $ j:=min\{i|v_{n+1}\rightarrow v_i\}\Rightarrow v_1\rightarrow\cdots\rightarrow v_{n+1} \rightarrow v_j \rightarrow \cdots \rightarrow v_n $

Due mezze righe, può andare bene.

[Tibor Gallai]

Due mezze righe, può andare bene.

Io la vedo in una riga!

Metodo alternativo:
fissato un nodo v, sia A l'insieme dei nodi a tali che a->v, e sia B l'insieme dei nodi b tali che v->b. Per ipotesi induttiva esistono i cammini Hamiltoniani P su A e Q su B. Allora noi percorriamo P->v->Q.