CONOSCERE CONOSCERSI
COMUNICARE
Nikolaus
Disegnare la casa di Babbo Natale non
staccando mai la penna dal foglio e non
ripassando mai sullo stesso lato.
Quante soluzioni ci sono?
Si deve seguire qualche
regola?
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
2
Soluzione
• 44
• Si deve partire dal basso
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
3
Ponti di königsberg
I cittadini di Königsberg, oggi Kaliningrad,
erano soliti passeggiare lungo le sponde del
fiume Pregel.
Possono farlo attraversando tutti i 7 ponti una
sola volta?
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
4
Aiuto
Il problema fu posto al matematico svizzero
Leonhard Euler il quale nel 1736 ne
formulò la soluzione.
Il problema può essere rappresentato con un
grafo
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
5
Grafo dei ponti
• il numero nel nodo indica
il numero di collegamenti
= grado
• se un nodo è di passaggio
il grado deve essere pari
• un nodo di grado dispari è
la partenza o la fine del
cammino
3
5
3
3
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
6
Conclusione
Non esiste un cammino che attraversi
tutti i ponti perché il numero di nodi
dispari è > 2 !
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
7
Passeggiate di Eulero
Cammino euleriano = un cammino che
partendo da un vertice utilizzi tutti i lati del
grafo una sola volta
Circuito euleriano = cammino euleriano in
cui la partenza coincide con il traguardo
e allora?….
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
8
Teorema di Eulero
Dato un grafo G(V, E) connesso:
• se esistono solo due vertici di grado
dispari allora esiste un cammino euleriano
di G
• se tutti i nodi sono di grado pari allora
esiste un circuito euleriano di G.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
9
Risposte
• Casa di babbo Natale ha soluzione perché
ha solo 2 nodi dispari.
• I ponti Königsberg non ha soluzione
perché ha 4 nodi dispari.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
10
Altri problemi
Trovare i cammini euleriani
tre quadrati
Parte Quinta
quattro cerchi
Conoscere - Conoscersi - Comunicare
Sonia Fiori
11
Strategia
Questi tipi di giochi furono proposti da Lewis
Carroll (tre quadrati) e T.H. O’Beirne di
Glasgow (quattro cerchi) trovò un metodo
rapido per risolverli:
si colorano alternativamente le regioni, il
cammino è il contorno della superficie
colorata.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
12
Soluzioni
Il contorno è un circuito euleriano
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
13
Ottaedro
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
14
Applicazioni dei cammini euleriani
•
•
•
•
Distribuzione della posta
pulizia delle strade
raccolta nettezza urbana
ispezione e manutenzione sistemi
distribuiti: reti elettriche, telefoniche,
stradali
• ……
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
15
Esempio raccolta nettezza urbana
Esiste un percorso economico?
• se tutti gli incroci hanno un numero pari di strade si!
• se gli incroci dispari sono 2 si!
• se il numero di incroci di grado dispari (strade senza
uscita) è maggiore di 2 ?
Come si possono accoppiare gli incroci critici in modo
più economico? cioè in modo che il cammino sia
minimo?……Algoritmo di Mei-Ko Kwan, cinese,
del 1962 famoso con il nome “problema del postino
cinese”.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
16
Le cose si complicano
..… e se alcune strade sono a senso unico?
non esiste ancora un algoritmo efficiente che
risolve il caso in generale.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
17
Parole chiave
•
•
•
•
Grado di un nodo
Cammino di Eulero
Circuito di Eulero
Teorema di Eulero
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
18
Fine
quinta parte
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
19
Leonhard Euler
(Basilea, in Svizzera, il 15 aprile 1707- S. Pietroburgo,
in Russia, il 18 settembre 1783)
Conosciuto in Italia con il nome di Eulero, produsse
moltissime opere, 88 volumi
in vari campi (ottica, nautica,
acustica, idraulica,..). Lo colpì
la cecità già dall’età di 30 anni.
Padre di molte notazioni
divenute standard , e, i,.. e
della più bella formula della
matematica
i
…...
e 1  0
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
20
Le miss della matematica
i
Le più belle formule
• Formula di Eulero
e 1  0
• Teorema di Fermat
l’equazione non ha soluzioni
intere per n>2
x y z
n
n
n
• e l’ultima……..
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
21
la neonata superformula
la superformula della natura scoperta dal botanico Johan
Gielis nel 2003
per ulteriori informazioni:
www.matematicamente.it/cimolin/formula/formula19.htm
oppure
http://users.quipo.it/base5/analisi/superforma.htm
tornare indietro
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
22
Pierre Fermat
(Francia Agosto 1601-1665)
Letterato e giurista si occupò di
matematica per diletto.
Nel margine di un libro scrive
“ho scoperto una
dimostrazione veramente
bella che questo margine è
troppo piccolo per
contenere”. Ma….
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
23
Andrew Wiles (Cambridge 11 Aprile 1953)
…occorreranno più di 300 anni per
trovare la dimostrazione di
questo teorema.
Nel 1995 Andrew Wiles, dopo 7
anni di lavoro, dimostra il
teorema di Fermat, la
dimostrazione è circa 200 pagine
ed è oltre la comprensione della
maggior parte dei matematici di
oggi.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
24
Lewis Carroll
(Inghilterra, Daresbury 27 Gennaio 1832 Guildford 14 Gennaio 1898)
Charles Lutwidge Dodgson, più noto
con lo pseudonimo di Lewis Carroll,
famoso scrittore inglese nonché,
matematico, logico e fotografo,
celebre soprattutto per “Alice’s
Adventures in Wonderland”.
Insegnò matematica, con una certa
apatia, per 26 anni.
Parte Quinta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
25