Newsgroup: it.hobby.enigmi
Titolo: Grafi doppi

Tutti sanno che è impossibile disegnare un quadrato con le
sue diagonali con un solo tratto di penna, passando una
sola volta su ogni segmento. La teoria dei grafi ci spiega,
poi, che possiamo farlo soltanto per quei grafi che hanno
un massimo di due nodi dispari e il quadrato con le diagonali
ha 4 nodi dispari. La stessa teoria ci dice anche che tutti i
grafi con nodi pari sono percorribili con un sol tratto di
penna e una mappatura a due colori ci dà un algoritmo
per risolvere qualunque di questi grafi.
Ma se vi chiedessi di passare esattamente due volte per
ogni segmento? E' facile verificare che ora il quadrato
suddetto è risolvibile, senza neppure impegnarsi troppo.
Verrebbe da dire che, passando due volte su ogni segmento,
siano risolvibili grafi fino a 4 nodi dispari. Invece è molto
meglio. Prendiamo ad es. gli spigoli di un cubo. E' possibile?
Direi proprio di si. Facciamone il grafo 2D:
A__________ B
|\         /|
| \       / |
|  \C___D/  |
|   |   |   |
|   |___|   |
|  /E   F\  |
| /       \ |
|/_________\|
G           H
(per vedere l'ascii-art usare caratteri fissi)
Una soluzione ad es. è:
ABHGECDFEGACDBHFDBACEFHGA
con ritorno al punto di partenza.
Allora qualunque grafo è percorribile in questa
maniera, ritornando al punto di partenza? O c'è
un criterio per dire quali grafi sì e quali no?
[Domande di cui ignoro la risposta.]
Perché m'interessa tanto? Dovete sapere che da qualche
giorno sono stato contagiato dal virus della polyhedron
mania e, poiché non mi posso permettere il lusso della
confezione di geomax che vorrei, sto cercando vari
modi economici per costruire poliedri. Un modo è quello
di usare cannucce *cucite* da un filo elastico che li
percorre tutte ritornando al punto di partenza, dove potrò
fare il nodo conclusivo. Come avete visto per il cubo
c'è senza dubbio almeno una soluzione, ma ora vorrei
dedicarmi ad un solido più complesso, isostatico, come
ad es. l'icosaedro.
Ecco, se non trovate una legge generale, datemi almeno
la soluzione per l'icosaedro!
Ciao!!!  :o))


devo aver letto la risposta da qualche parte:
o meglio: so che ogni grafico è percorribile passando esattamente 2 
volte su ogni segmento. la risposta l'ha data Euler. infatti si possono 
percorrere con un solo tratto solo grafi che hanno 0 o 2 nodi dispari.
ma se posso usare 2 tratti, allora tutti i nodi sono pari. e quindi è 
percorribile.
sulla condizione relativa al tornare al punto iniziale, devo pensarci 
ancora un po'... :-)
-- 
Stefano 'pazqo' Pascolutti
http://www.pazqo.altervista.org
http://www.artofproblemsolving.com/LaTeX/AoPS_L_TeXer.php

 ancora un po'... :-)
E con solo nodi pari, si può sempre tornare al punto di partenza!
Non solo, ma si può applicare sempre il metodo della mappa
a due colori per trovare velocemente una soluzione.
Non mi resta che andare a comperare una mazzetta di
cannucce colorate, quelle delle bibite, un filo elastico e
un ago da materassaio. Anche questa volta me la caverò
con pochi euro.  :o))
Ciao!!!

 percorribile.
Quindi per sostenere un poliedro con nodi pari basta un filo in ciascuna 
cannuccia, in quelli con nodi dispari occorrono due fili per cannuccia.
Potrebbe significare che il primo è in qualche modo più stabile?
In un altro thread ho provato ad arrivare alle stesse conclusioni da un 
diverso punto di vista: chissà se le cose sono in qualche modo 
collegate.
ciao
paolo