Il mitico ritorno del commesso viaggiatore

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Anér
Messaggi: 722
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Il mitico ritorno del commesso viaggiatore

Messaggio da Anér » 04 set 2009, 14:07

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?
Sono il cuoco della nazionale!

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 04 set 2009, 15:18

[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

didudo
Messaggi: 123
Iscritto il: 22 mag 2009, 10:45
Località: pisa

Messaggio da didudo » 04 set 2009, 21:11

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?
pensavo fosse il forum "belli e abbronzati"....

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 04 set 2009, 21:33

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

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 04 set 2009, 21:58

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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 04 set 2009, 22:58

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

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 04 set 2009, 23:06

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.
Ultima modifica di Tibor Gallai il 04 set 2009, 23:32, modificato 1 volta in totale.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Messaggio da dario2994 » 04 set 2009, 23:19

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

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 04 set 2009, 23:26

Un grafo orientato in cui ogni coppia di nodi è collegata da un arco.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 04 set 2009, 23:32

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
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 04 set 2009, 23:33

Sì, mi stavo accorgendo di questo un attimo fa, ho editato.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 04 set 2009, 23:36

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

Avatar utente
Anér
Messaggi: 722
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Messaggio da Anér » 05 set 2009, 11:38

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.
Sono il cuoco della nazionale!

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 05 set 2009, 15:38

Anér ha scritto:Due mezze righe, può andare bene.
Io la vedo in una riga! 8)

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.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]

Rispondi