classico aggiornato

[psion_metacreativo]

Ispirato da un classico:

Nell'arcipelago di Amoit Anazit ci sono diciannove isole collegate tra loro da alcuni ponti. Da ogni isola si può raggiugere qualsiasi altra isola attraversando non più di tre ponti. La prima isola ha un ponte, la seconda ne ha due, la terza tre, e così via fino alla diciannovesima che ne ha diciannove. Dimostrare che se Giuseppe riesce a fare una passeggiata attraversando ogni ponte una e una sola volta, allora il poligono non intrecciato (i cui lati non si intersecano) che ha per vertici le isole ha un angolo di 2005 radianti. (Considerare la terra perfettamente sferica e i ponti arbitrariamente lunghi).

[Hammond]

Ma allora ci può essere anche più di un ponte tra due isole? (anche perchè se no non si sa dove far arrivare l'ultimo ponte della diciannovesima isola..)

[psion_metacreativo]

Certo che ci può essere più di un ponte tra due isole

[ReKaio]

Nell'arcipelago di Amoit Anazit ci sono diciannove isole collegate tra loro da alcuni ponti. Da ogni isola si può raggiugere qualsiasi altra isola attraversando non più di tre ponti. La prima isola ha un ponte, la seconda ne ha due, la terza tre, e così via fino alla diciannovesima che ne ha diciannove. Dimostrare che se Giuseppe riesce a fare una passeggiata attraversando ogni ponte una e una sola volta, allora il poligono non intrecciato (i cui lati non si intersecano) che ha per vertici le isole ha un angolo di 2005 radianti. (Considerare la terra perfettamente sferica e i ponti arbitrariamente lunghi).

devi percorrere il grafo che ha come nodi le isole e come archi i ponti, ma siccome ci sono più di 2 nodi dispari (numero dispari di archi uscenti), allora non esiste una cammino che passa per tutti gli archi.

forse ho interpretato male il testo

[psion_metacreativo]

No no è corretto Kaio è una proposizione vera a vuoto... I love logic...

Il punto interessante sarebbe dimostrare perchè:

[...] siccome ci sono più di 2 nodi dispari (numero dispari di archi uscenti), allora non esiste una cammino che passa per tutti gli archi.

e questo è l'aspetto classico del problema, il resto poco più che fumo negli occhi.

[ReKaio]

def: Linea di Eulero, cammino che percorre ogni arco di un grafo una ed una sola volta (folcloristico)

th1: un grafo connesso con i gradi di ogni vertice pari ha una linea di Eulero.

dimostrazione molto poco rigorosa e molto poco formale
prendi un grafo con tutti i vertici pari. inizia un percorso K a caso, da un vertice A ogni volta che entri in un nuovo vertice, esci da uno degli archi ancora non percorsi, finché è possibile farlo. gli archi sono in numero finito, quindi prima o poi dovrai fermarti. siccome in ogni vertice ci sono un numero pari di archi, c'è sempre un arco da cui sia possibile uscire, tranne quando sei tornato nel vertice iniziale, allora il tuo cammino casuale si interrompre appunto in A, ed è un ciclo.
Se il cammino passa per ogni arco, allora abbiamo il cammino che si cercava. altrimenti prendo un vertice B in cui ci siano 2 o più archi non percorsi, ed inizio un nuovo cammino casuale K' solo su archi non percorsi da K. gli archi rimasti saranno ancora pari su ogni vertice, quindi il cammino tornerà in B per ragioni analoghe alle precedenti. con il percorso K' posso ampliare K, K-->AB-K'-BA.
iterando il processo, siccome ogni volta che aggiungo un nuovo cammino a quelli già considerati, elimino almeno 2 archi, in un tempo finito avrò costruito un simpatico cammino di eulero. (prima o poi, arrivo al grafo vuoto, togliendo sempre archi, l'unico caso in cui i vertici sono tutti pari e non posso aggiungere nuovi cicli)

th2: un grafo connesso possiede un cammino da A a B che copra tutti gli archi una e una sola volta se e solo se A e B sono i soli vertici dispari.

collego A a B, costruisco il cammino di prima ^^ eliminando AB ho il cammino cercato

_scusate il delirio_

[MindFlyer]

con il percorso K' posso ampliare K, K-->AB-K'-BA.

Non è chiaro, in che modo ampli K?
Questo teorema sarebbe da mettere nel Glossario.
Magari provvedo io, avevo una dimostrazione molto concisa.

[ReKaio]

con il percorso K' posso ampliare K, K-->AB-K'-BA.

Non è chiaro, in che modo ampli K?
Questo teorema sarebbe da mettere nel Glossario.
Magari provvedo io, avevo una dimostrazione molto concisa.

ho il mio ciclo K che parte e finisce in A, un altro ciclo K' che ha in comune con K solo il vertice B

parto da A, vado fino a B seguendo K
percorro K' tornando in B
finisco K tornando in A, ed ho un ciclo strettamente più lungo

(comunque è una finta dimostrazione, niente di serio)

in effetti ragionando per assurdo sul cammino ciclico di lunghezza massima è molto più carino

[psion_metacreativo]

Le idee sono sostanzialmente quelle esposte da Kaio ma chi vuol metter un po' più di formalismo in tutto ciò? Personalmente apprezzo la disponibilità di Mind ad inserire il teorema nel glossario, magari ampliando il topic di Marco sulla teoria dei grafi...

[MindFlyer]

ho il mio ciclo K che parte e finisce in A, un altro ciclo K' che ha in comune con K solo il vertice B

Se K e K' hanno almeno un vertice in comune, ok. Ma se non ne hanno?
Bisogna far vedere che K ha sempre un nodo B da cui partono archi non ancora esplorati, per via della connessione, e costruire il nuovo ciclo a partire da B.
Un altro problema è che dopo aver tolto K, il grafo potrebbe a priori non essere più connesso, quindi al passo successivo quest'ipotesi non può più essere usata!

[Catraga]

Non per fare il saccente , ma in teoria dei grafi, non si dice "linea di Eluer" , ma "cammino euleriano" se trattasi di ciclo (punto di partenza e termine coincidono), altrimenti "tratta o passeggiata euleriana" se non si tratta di ciclo.
Un cammino euleriano su G, grafo connesso, esiste se e solo se tutti i vertici del grafo hano grado pari.
Una tratta euleriana su G, grafo connesso, esiste se e solo se al piu' due vertici hanno grado dispari. (Ovvio che se ce ne e' uno di grado dispari ce ne devono essere due -elementare esercizio sul test di parita').