Il mitico ritorno del commesso viaggiatore
Il mitico ritorno del commesso viaggiatore
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?
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!
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Vedi anche:
viewtopic.php?t=12361
viewtopic.php?t=12361
[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]
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.
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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.
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]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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]
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
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.
Due mezze righe, può andare bene.
Sono il cuoco della nazionale!
-
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12
Io la vedo in una riga!Anér ha scritto:Due mezze righe, può andare bene.
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]