Problema dei ponti di Königsberg: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Etichetta: Annullato |
m Annullate le modifiche di 79.27.7.215 (discussione), riportata alla versione precedente di FrescoBot Etichetta: Rollback |
||
Riga 18:
== Rappresentazione ==
Eulero rappresentò la disposizione dei sette ponti congiungendo con altrettante linee le quattro grandi zone della città, come nella prima immagine. Si noti che dai nodi A, B e D partono (e arrivano) tre ponti; dal nodo C, invece, cinque ponti. Questi sono i gradi dei nodi: rispettivamente, 3, 3, 5, 3.<br />Prima di raggiungere una conclusione, Eulero ha ipotizzato delle situazioni diverse di zone e ponti (nodi e collegamenti): con quattro nodi e quattro ponti è possibile partire, ad esempio, da A, e tornarci passando per tutti i ponti una e una sola volta. Il grado di ciascun nodo è un numero pari. Se invece si parte da A per arrivare a D, ogni nodo è di grado pari a eccezione di due nodi, di grado dispari (uno). Sulla base di queste osservazioni, Eulero ha enunciato il seguente teorema:
:''Un qualsiasi grafo è percorribile se e solo se ha tutti i nodi di grado pari, o due di essi sono di grado dispari; per percorrere un grafo "possibile" con due nodi di grado dispari, è necessario partire da uno di essi, e si terminerà sull'altro nodo dispari''.
[[File:Leonhard Euler.jpeg|thumb|[[Eulero]] a 49 anni, dipinto da [[Emanuel Handmann]] (1756)]]
Pertanto è impossibile percorrere Königsberg come richiesto dalla tesi, poiché tutti i nodi sono di grado dispari.
Va osservato che la teoria dei grafi ha strette connessioni con la [[topologia]]: la forma di un grafo, o meglio di una [[raffigurazione di un grafo]] o di una sua variante (v. [[grafo arricchito]]) può essere modificata spostando i vertici e distorcendo le linee che li collegano, pur di mantenere i collegamenti effettivi. Non conta se un collegamento si presenta rettilineo o curvato e neppure se un vertice sta da una parte o dall'altra rispetto a un collegamento di vertici vicini.
Eulero ha dimostrato che per un grafo qualsiasi un cammino con le caratteristiche desiderate è possibile se e solo se il grafo non ha vertici (i punti nella raffigurazione del grafo) che sono raggiunti da un numero dispari di spigoli. Un tale cammino è chiamato [[cammino euleriano|circuito euleriano]]. Dato che il grafo relativo a Königsberg ha quattro di tali vertici, il cammino non esiste.
Se si lascia cadere la richiesta che il punto di inizio e il punto finale coincidano, allora vi possono essere nessuno o due vertici toccati da un numero dispari di spigoli. Un tale cammino viene chiamato ''[[cammino euleriano]]''.
Tra i grafi euleriani ricordiamo tutti grafi completi di ordine dispari, la [[stella di David]] e le scimitarre di Allah. Nessuno dei grafi completi di ordine pari è invece euleriano.
Per un esame solo matematico del problema v. [[multigrafo euleriano]].
== Importanza nella storia della matematica ==
| |||