Grafi in gita

[pennywis3]

Sbollita la delusione per non aver potuto partecipare alle olimipadi dei piccoli Einstein, e passata la stanchezza per essere tornato dalla gita, con tutto lo zelo che trovo posto questo simpatico problemino.
<BR>
<BR>Versione 1.1) Dato un grafo di n vertici, completo e orientato, dimostrare che esiste una permutazione di vertici (a[1],a[2],...,a[n]) tale che a[1]->a[2]->a[3]->...->a[n].
<BR>
<BR>Per chi non conoscesse alcune proprieta dei grafi, potete risolvere la seguente versione equivalente.
<BR>
<BR>Versione 1.2) In uno stato ci sono n città, ognuna delle quali è collegata ad ogni altra tramite una strada. Le strade sono a senso unico. Dimostrare che è possibile determinare un percorso (legale, senza andare contromano) che permetta di visitare in macchina tutte le n città passando una sola volta per ognuna di queste.
<BR>
<BR>
<BR>~p3~ (p3pp3 p3pp3pp3pp3\'...)
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: pennywis3 il 18-04-2003 13:49 ]

[pennywis3]

UP

[Fede_HistPop]

Com\'è che hai la mania dei grafi, pennywis3?

[pennywis3]

Lo so, è una strana perversione...
<BR>
<BR>Scherzi a parte, il fatto che ultimamente abbia postato problemi di questo tipo è un caso... come argomento mi piace, perchè raramente puoi risolvere un problema di questo tipo con la forza...
<BR>
<BR>
<BR>~p3~

[alberto]

riformulo(spero che pennywis3 non se la prenda):
<BR>dimostra che in un grafo completo orientato vi è una catena orientata che tocca tutti i vertici una e una sola volta.
<BR> prendiamo la catena orientata (A[1],A[2],...,A[h],A[h+1]) di lunghezza massima del grafo di n vertici e dimostriamo per assurdo che questa non può che essere di lunghezza n-1.
<BR>se essa non fosse di lunghezza n-1, ma di lunghezza h minore di n-1, ci saranno dei vertici esterni alla catena e per ogni vertice (P) esterno alla catena si avrebbe che non può esservi lo spigolo PA[1] nè lo spigolo A[h+1]P altrimenti la catena avrebbe lunghezza maggiore di h.
<BR>ci saranno quindi gli spigoli A[1]P e PA[h+1].
<BR>esisteranno quindi due vertici consecutivi A[x], A[x+1], tali che esistono gli spigoli A[x]P e PA[x+1]. in questo modo abbiamo trovato una catena lunga h+1 (la catena A[1],...,A[x],P,A[x+1],...,A[h+1])
<BR>assurdo.
<BR>la catena deve essere lunga n-1, quindi deve toccare una e una sola volta tutti gli n punti<BR><BR>[ Questo Messaggio è stato Modificato da: alberto il 19-04-2003 14:42 ]

[pennywis3]

Bueno, mi piace.
<BR>Io l\'ho dimostrato per induzione su n. Se n=3 il risultato è banale. Poniamo che la cosa valga per ogni k<=n. Consideriamo ora un grafo con k+1 vertici, e separiamone k. All\'interno di questo sottografo ci sarà una catena orientata C:a[1]->...->a[k]. Consideriamo ora tutti i collegamenti tra il k+1esimo vertice P e quelli della catena. Prendiamo il minimo indice i che contrassegni un vertice a della catena tale che P->a; per la minimalità di i si avrà che a[i-1]->P e così la catena a[1]->...->a[i-1]->P->a->...->a[k] è quella cercata. Se i=1 la catena risulta essere P->C, mentre se tale i non esiste la catena cercata sarà C->P
<BR>
<BR>~p3~