Considerato questo problema, nel 1736 Eulero dimostrò che ciò era impossibile, e considerò un problema più generale: quali aree, separate da rami di fiume e collegate da ponti, possono essere percorse visitando ciascun ponte esattamente una volta, e quali sono impossibili.
Ponti di Königsberg">
Modifichiamo leggermente il problema. Indicheremo ciascuna delle aree in esame, separate da un fiume, con un punto, e i ponti che le collegano con un segmento di linea (non necessariamente una linea retta). Quindi, invece di un piano, lavoreremo semplicemente con una certa figura composta da segmenti di curve e linee rette. Nella matematica moderna, tali figure sono chiamate grafici, i segmenti sono chiamati bordi e i punti che collegano i bordi sono chiamati vertici. Allora il problema originario è equivalente al seguente: è possibile tracciare un dato grafico senza staccare la matita dal foglio, cioè in modo tale che ciascuno dei suoi bordi venga superato esattamente una volta?
Tali grafici, che possono essere disegnati senza staccare la matita dal foglio, sono chiamati unicursali (dal latino unus cursus - un percorso), o euleriani. Allora il problema si pone così: a quali condizioni un grafo è unicursale? È chiaro che un grafo unicursale non cesserà di essere unicursale se viene modificata la lunghezza o la forma dei suoi bordi, così come viene modificata la posizione dei vertici, purché la connessione dei vertici tramite i bordi non cambi (in il senso che se due vertici sono collegati, dovrebbero rimanere connessi, e se sono separati – allora disconnessi).
Se un grafo è unicursale, anche il grafo topologicamente equivalente sarà unicursale. L'unicursità è quindi una proprietà topologica di un grafo.
Innanzitutto dobbiamo distinguere i grafi connessi da quelli disconnessi. Le figure connesse sono quelle tali che due punti qualsiasi possono essere collegati da un percorso appartenente a questa figura. Ad esempio, la maggior parte delle lettere dell'alfabeto russo sono collegate, ma la lettera Y no: è impossibile spostarsi dalla sua metà sinistra a destra lungo i punti appartenenti a questa lettera. La connessione è una proprietà topologica: non cambia quando la figura si trasforma senza rotture o incollaggi. È chiaro che se un grafo è unicursale allora deve essere connesso.
In secondo luogo, considera i vertici del grafico. Chiameremo indice di un vertice il numero di spigoli trovati in questo vertice. Ora chiediamoci: a cosa possono essere uguali gli indici dei vertici di un grafo unicursale?
In questo caso possono esserci due casi: la linea che traccia il grafico può iniziare e finire nello stesso punto (chiamiamolo “percorso chiuso”), o magari in punti diversi (chiamiamolo “percorso aperto”). Prova a disegnare tu stesso tali linee - con qualsiasi autointersezione desideri - doppia, tripla, ecc. (per chiarezza, è meglio che non ci siano più di 15 bordi).
È facile vedere che in un percorso chiuso tutti i vertici hanno un indice pari, e in un percorso aperto esattamente due hanno un indice dispari (questo è l'inizio e la fine del percorso). Il fatto è che se un vertice non è quello iniziale o quello finale, allora, arrivati ad esso, bisogna poi uscirne - quindi, quanti spigoli entrano in esso, lo stesso numero ne esce, e il numero totale di entranti e uscenti i bordi saranno uniformi. Se il vertice iniziale coincide con il vertice finale, allora anche il suo indice è pari: il numero di spigoli che ne sono usciti, lo stesso numero di quelli che sono entrati. E se il punto di partenza non coincide con il punto finale, allora i loro indici sono dispari: devi uscire una volta dal punto di partenza e poi, se torniamo ad esso, uscire di nuovo, se torniamo di nuovo, uscire di nuovo, ecc. .; ma bisogna arrivare a quello finale, e se poi lo lasciamo, allora bisogna ritornare di nuovo, ecc.
Quindi, affinché un grafo sia unicursale, è necessario che tutti i suoi vertici abbiano un indice pari oppure che il numero di vertici con indice dispari sia uguale a due.
 |
Calcola gli indici dei suoi vertici e assicurati che non possa essere unicursale. Ecco perché non ci sei riuscito quando volevi fare il giro di tutti i ponti...
Sorge la domanda: se un grafo connesso non ha vertici con un indice dispari o esattamente due di questi vertici, allora il grafo è necessariamente unicursale? Si può dimostrare rigorosamente che sì! Pertanto, l'unicurità è correlata univocamente al numero di vertici con indice dispari.
Esercizio: costruisci un altro ponte sullo schema dei ponti di Königsberg - dove vuoi - in modo che i ponti risultanti possano essere girati, dopo averli visitati esattamente una volta; segui davvero questa strada.
Ora ce n'è un altro fatto interessante: Si scopre che qualsiasi sistema di aree collegate da ponti può essere aggirato se è necessario visitare ciascun ponte esattamente due volte! Prova a dimostrarlo tu stesso.
| NOTIZIE DEL FORO Teoria dei Cavalieri dell'Etere | 01.10.2019 - 05:20: -> - Karim_Khaidarov. 30.09.2019 - 12:51: |
I 7 ponti della città di Kaliningrad (Koningsberg) portarono alla creazione della cosiddetta teoria dei grafi di Leonhard Euler.
Un grafico è un certo numero di nodi (vertici) collegati da bordi. Due isole e le sponde del fiume Pregel, dove si trovava, erano collegate da 7 ponti. Il famoso filosofo e scienziato I. Kant, camminando lungo i ponti di Königsberg, si avvicinò a un problema noto a tutti nel mondo come il problema dei “7 ponti di Königsberg”: è possibile attraversare tutti questi ponti e allo stesso tempo tornare contemporaneamente al punto di partenza del percorso in modo da percorrere ogni ponte una sola volta?
Molti hanno provato a risolvere questo problema sia praticamente che teoricamente. Ma nessuno ci è riuscito. Pertanto, si ritiene che nel XVII secolo i residenti abbiano iniziato una tradizione speciale: quando si cammina per la città, attraversare tutti i ponti una sola volta. Ma, naturalmente, nessuno ci è riuscito.
Nel 1736, questo problema interessò lo scienziato Leonhard Euler, un matematico eccezionale e famoso e membro dell'Accademia delle Scienze di San Pietroburgo, che riuscì a trovare una regola grazie alla quale era possibile risolvere questo enigma. Nel corso dei suoi giudizi, Eulero trasse le seguenti conclusioni: 1. il numero di vertici dispari (vertici a cui conduce un numero dispari di spigoli) del grafico deve essere pari. Non può esistere un grafo che abbia un numero dispari di vertici dispari. 2. Se tutti i vertici del grafico sono pari, puoi disegnare un grafico senza sollevare la matita dal foglio e puoi iniziare da qualsiasi vertice del grafico e terminarlo nello stesso vertice. 3. Un grafico con più di 2 vertici dispari non può essere disegnato con un solo tratto.
Ciò porta alla conclusione che è impossibile attraversare tutti e sette i ponti senza attraversarne uno due volte. Successivamente, questa teoria dei grafi divenne la base per la progettazione di sistemi di comunicazione e trasporto e divenne ampiamente utilizzata nella programmazione, nell'informatica, nella fisica, nella chimica e in molte altre scienze e campi.
È interessante notare che gli storici credono che ci sia una persona che ha risolto questo problema, che è stata in grado di attraversare tutti i ponti solo una volta, anche se in teoria...
Ed è stato così. Il Kaiser (cioè l'imperatore) Guglielmo era famoso per la sua semplicità di pensiero, franchezza e "chiusura mentale". Una volta divenne quasi vittima di uno scherzo che l'ingegno gli giocò: i burloni mostrarono al Kaiser una mappa della città di Königsberg e gli chiesero di provare a risolvere questo famoso problema, che, per definizione, era irrisolvibile. Ma Kaiser ha chiesto solo un pezzo di carta e una penna, specificando che avrebbe risolto il problema in appena un minuto e mezzo. Gli scienziati rimasero stupiti - Wilhelm scrisse: "Ordino la costruzione dell'ottavo ponte sull'isola di Lomze". Questo è tutto, il problema è risolto... E così a Kaliningrad è apparso un nuovo ottavo ponte sul fiume, chiamato in onore del Kaiser. Anche un bambino può risolvere il problema con otto ponti...
Sapevi che i sette ponti della città di Koeningsberg (ora questa città si chiama Kaliningrad) sono diventati i "colpevoli" della creazione della teoria dei grafi di Leonhard Euler (un grafico è un certo numero di nodi (vertici) collegati da bordi) . Ma come è potuto succedere?
Due isole e sponde del fiume Pregel, su cui sorgeva Koeningsberg, erano collegate da 7 ponti. Il famoso filosofo e scienziato Immanuel Kant, passeggiando lungo i ponti della città di Königsberg, pose un problema noto a tutti nel mondo come il problema dei 7 ponti di Königsberg: è possibile attraversare tutti questi ponti e allo stesso tempo ritornare al punto di partenza del percorso in modo da attraversare ogni ponte una sola volta. Molti hanno provato a risolvere questo problema sia praticamente che teoricamente. Ma nessuno ci riuscì, né fu possibile dimostrare che ciò fosse impossibile anche teoricamente. Pertanto, secondo i dati storici, si ritiene che nel XVII secolo i residenti formassero una tradizione speciale: passeggiando per la città, attraversare tutti i ponti una sola volta. Ma, come sai, nessuno ci è riuscito.
Nel 1736, questo problema interessò lo scienziato Leonhard Euler, un matematico eccezionale e famoso e membro dell'Accademia delle scienze di San Pietroburgo. Ne scrisse in una lettera al suo amico, lo scienziato, ingegnere e matematico italiano Marioni, datata 13 marzo 1736. Trovò una regola con la quale poteva facilmente e semplicemente ottenere una risposta a questa domanda di interesse per tutti. Nel caso della città di Koeningsberg e dei suoi ponti ciò si è rivelato impossibile.
Nel processo del suo ragionamento, Eulero arrivò alle seguenti conclusioni teoriche:
Il numero di vertici dispari (vertici a cui conduce un numero dispari di spigoli) del grafico deve essere pari. Non può esistere un grafo che abbia un numero dispari di vertici dispari.
Se tutti i vertici del grafico sono pari, puoi disegnare un grafico senza sollevare la matita dal foglio e puoi iniziare da qualsiasi vertice del grafico e terminarlo nello stesso vertice.
Un grafico con più di 2 vertici dispari non può essere disegnato con un solo tratto 
Se consideriamo questa regola per i 7 ponti di Koeningsberg, le parti della città nella figura (grafico) sono indicate dai vertici e i ponti sono indicati dai bordi che collegano questi vertici. Il grafico dei 7 ponti di Königsberg aveva 4 vertici dispari (ovvero, tutti i suoi vertici erano dispari), quindi è impossibile attraversare tutti e 7 i ponti senza attraversarne nessuno due volte.
Sembrerebbe che una scoperta così insolita non possa avere alcuna reale applicazione o beneficio pratico. Ma è stato trovato un uso, e anche altro. La teoria dei grafi, creata da Leonhard Euler, ha costituito la base per la progettazione dei sistemi di comunicazione e trasporto; è utilizzata nella programmazione e nell'informatica, nella fisica, nella chimica e in molte altre scienze e campi.
Ma la cosa più interessante è che gli storici credono che ci sia una persona che ha risolto questo problema; è riuscita ad attraversare tutti i ponti solo una volta, anche se in teoria, ma la soluzione c'era... Ed è così che è successo...
Il Kaiser (imperatore) Guglielmo era famoso per la sua semplicità di pensiero, la franchezza e la "mestrezza mentale" militaresca. Un giorno, durante un evento mondano, per poco non rimase vittima di uno scherzo che le menti dotte presenti al ricevimento decisero di fargli. Mostrarono al Kaiser una mappa della città di Königsberg e gli chiesero di provare a risolvere questo famoso problema, che, per definizione, era semplicemente irrisolvibile. Con sorpresa di tutti, il Kaiser chiese un pezzo di carta e una penna, specificando allo stesso tempo che avrebbe risolto questo problema in appena un minuto e mezzo. Gli scienziati sbalorditi non potevano credere alle loro orecchie, ma gli furono rapidamente trovati inchiostro e carta. Il Kaiser mise il pezzo di carta sul tavolo, prese una penna e scrisse: "Ordino la costruzione dell'ottavo ponte sull'isola di Lomze". E tutto il problema è risolto.....
È così che è apparso un nuovo ottavo ponte sul fiume nella città di Königsberg, chiamato Ponte Kaiser. E adesso anche un bambino può risolvere il problema con 8 ponti .
Soluzioni non convenzionali al problema
La "soluzione" di Kaiser
Sulla mappa dell'antica Königsberg c'era un altro ponte, apparso poco dopo, che collegava l'isola di Lomse con il lato meridionale. Questo ponte deve la sua comparsa allo stesso problema di Eulero-Kant. Ciò è accaduto nelle seguenti circostanze.
L'imperatore Guglielmo era noto per la sua schiettezza, semplicità di pensiero e "ottusità" militare. Un giorno, durante un evento mondano, per poco non rimase vittima di uno scherzo che le menti dotte presenti al ricevimento decisero di fargli. Mostrarono al Kaiser una mappa di Königsberg e gli chiesero di provare a risolvere questo famoso problema, che per definizione era irrisolvibile. Con sorpresa di tutti, il Kaiser chiese una penna e un pezzo di carta, dicendo che avrebbe risolto il problema in un minuto e mezzo. L'establishment tedesco, sbalordito, non poteva credere alle proprie orecchie, ma carta e inchiostro furono rapidamente trovati.
Il Kaiser mise il pezzo di carta sul tavolo, prese una penna e scrisse quanto segue: "Ordino la costruzione dell'ottavo ponte sull'isola di Lomze". Ecco come è apparso a Königsberg nuovo ponte, che veniva chiamato il “Ponte Kaiser”. E adesso anche un bambino potrebbe risolvere il problema con otto ponti.
Guarda anche
Letteratura
Fondazione Wikimedia. 2010.
La città di Königsberg, sorta nel XIII secolo, era formalmente costituita da tre insediamenti urbani indipendenti, diversi insediamenti e città. Erano situati sulle rive e sulle isole del fiume Pregel, che divideva la città in quattro parti principali: Altstadt e Löbenicht, Kneiphof, Lomse, Fortstadt. Per la comunicazione e il commercio tra gli insediamenti urbani, nel XIV secolo iniziarono a essere costruiti ponti.
A causa del costante pericolo militare proveniente dalla Polonia e dalla Lituania, davanti a ciascuno dei ponti fu costruito un ponte difensivo o cosiddetto. Torre di avvistamento con cancello basculante o a soffietto in rovere con rivestimento in ferro battuto. E i ponti stessi acquisirono il carattere di strutture difensive.
I ponti erano sede di cortei, eventi religiosi e festivi e cortei, e negli anni del cosiddetto. "Nella prima epoca russa" (1758 - 1762), quando Koenigsberg divenne parte dell'Impero russo durante la Guerra dei Sette Anni, sui ponti si svolgevano processioni religiose ortodosse. Una volta tale processione religiosa era dedicata alla festa ortodossa della benedizione dell'acqua del fiume Pregel, che suscitò il genuino interesse degli abitanti indigeni di Koenigsberg.
All'inizio del XX secolo tutti e sette i ponti erano tirabili, ma a causa dell'indebolimento e del declino della navigazione lungo il fiume Pregel, i tre ponti sopravvissuti fino ad oggi non sono più tirabili.
Negozio Ponte, Krämerbrücke
Il più antico dei sette ponti di Königsberg è Ponte Lavochny(Krämerbrücke), che collegava la città di Altstadt (castello reale) e l'isola di Kneiphof.
Costruito nel 1286, nel 1900 fu costruito un nuovo ponte metallico sul sito del vecchio ponte di legno. Il nome del ponte indica che esso stesso e il territorio adiacente del fiume Pregolya erano una concentrazione di scambi commerciali.
All'ingresso del ponte è stata installata una statua di Hans Zagan, figlio di un calzolaio del Kneiphof. Secondo la leggenda, durante la battaglia tra le truppe dell'Ordine Teutonico e i Litvin vicino a Rudau (villaggio di Melnikovo, regione di Zelenograd), Hans raccolse lo stendardo dell'ordine dalle mani di un cavaliere ferito. I nazisti, saliti al potere in Germania nel 1933, per ragioni ideologiche e morali, demolirono il monumento a Zagan, perché era ebreo.
Nel 1972 fu demolito a causa della costruzione del ponte Estakadny.
Ponte Lavochny. Sullo sfondo ci sono i magazzini e l'area di carico della nave - Lastadie
Ponte Lavochny con magazzini-fienili portuali Speicher (Speicher) sull'argine destro del fiume Pregel. Distretti Laak e Hundegatt. A sinistra c'è l'isola Kneiphof
Ponte Verde, GrüneBrücke
Il secondo ponte più antico di Königsberg è Ponte Verde. Costruito nel 1322. Il ponte bruciò nel 1582, fu ricostruito nel 1590 ed esisteva in forma di legno fino al 1907, quando fu sostituito da un ponte di metallo.
Collegava l'isola Kneiphof e la zona di Fortstadt attraverso il vecchio ramo del fiume Pregolya da cui partire Castello reale al sobborgo di Ponart. Il nome stesso del ponte deriva dal colore della vernice utilizzata per dipingere le campate e i supporti del ponte.
Nel XVII secolo lo era Ponte Verde si sentirono lettere arrivare a Königsberg. In attesa della posta Ponte Verde Gli uomini d'affari della città si sono riuniti e, in attesa della corrispondenza, hanno discusso dei loro affari. Nel 1623, esattamente intorno Ponte Verde Viene costruita la Borsa commerciale di Koenigsberg.
Nel 1972, il Ponte Verde, come il Ponte Lavochny, cadde vittima del Ponte a Traliccio.
Ponte Verde. Vista dall'isola Kneiphof
Veduta del Ponte Verde e della Borsa Mercantile
Ponte Giblet (funzionante), Koettel brücke
Nel 1377, dopo i ponti Lavochny e Green, a monte dell'antico letto del fiume Pregel, Frattaglie O Lavoratore un ponte che collegava anche l'isola di Kneiphof e la zona di Forstadt.
Entrambe le opzioni di traduzione non sono ideali, perché... Il nome tedesco del ponte deriva dalla Sassonia e nella versione russa significa approssimativamente “ponte ausiliario, funzionante, destinato al trasporto dei rifiuti”. Molto probabilmente deve il suo nome al vicino mattatoio.
Nel 1886 quella in legno fu ricostruita in quella in ferro.
Durante la seconda guerra mondiale Ponte del Giblet fu distrutto e mai più ricostruito.
Ponte del Giblet. Veduta della Borsa Mercantile dall'Isola Kneiphof
Ponte del Giblet. Vista dal Ponte Verde
Ponte della fucina, Schmiderbrüke
Nel 1397, a Königsberg, a monte del nuovo letto del fiume Pregel, fu eretto il ponte della Forgia che, come il ponte Lavochny, collegava la città di Altstadt e l'isola di Kneiphof.
I fabbri erano tradizionalmente situati vicino a questo ponte sulle rive del fiume Pregel.
Nel 1787 il ponte era diventato molto usurato e fatiscente e fu sostituito da un nuovo ponte, anch'esso in legno. Nel 1896 fu eretto un nuovo ponte di metallo sul sito del vecchio ponte di legno.
Il Forge Bridge fu distrutto durante la seconda guerra mondiale e non fu mai ricostruito.
Ponte della fucina con torre di osservazione
Ponte Kuznechny
Ponte di legno, Holzbrücke
Nel 1404 fu costruito un ponte quadruplo tra Altstat e l'isola di Lomze, chiamato Wooden.
Sul Ponte di Legno c'era targa commemorativa con estratti dalla cronaca prussiana. La stessa opera in dieci volumi di Albrecht Lukhel David raccontava dell'antica Prussia pagana e della storia dell'Ordine Teutonico fino al 1410.
Nel 1904 fu eretto un nuovo ponte di metallo sul sito del vecchio ponte di legno, ma il nome del ponte rimase lo stesso. Il ponte di legno si è conservato in questa forma fino ai giorni nostri.
Ponte di Legno. Veduta dell'isola Kneiphof
Ponte Alto, Hohebrücke
Costruito a Königsberg nel 1520 per collegare l'isola di Lomse e la regione di Forstadt.
Fu ricostruita nel 1882, le sue parti in legno furono sostituite con quelle in metallo. Nello stesso anno, accanto a Ponte Alto Nella zona di Forstadt fu eretta una casa sul ponte. Questo bellissimo e piccolo edificio in stile neogotico è sopravvissuto fino ai giorni nostri.
Nel 1937 il vecchio fu smantellato e nelle vicinanze ne fu costruito uno nuovo in metallo con supporti in cemento. Da vecchio Ponte Alto I supporti in mattoni di cemento sono stati conservati.
Ponte Alto. Veduta dell'isola di Lomse
Ponte Alto. Vista dall'isola di Lomse al quartiere Forstadt
Ponte del miele, Honigbrücke
Il più giovane dei sette ponti di Königsberg collegava l'isola di Lomse con l'isola di Kneiphof.
Esistono diverse versioni sull'origine del nome Ponte del miele. Secondo uno di loro Besenrode, membro del municipio di Kneiphof, avrebbe pagato la costruzione del ponte con barili di miele, in un altro modo il miele sarebbe stato utilizzato per pagare la costruzione di una stazione commerciale vicino al ponte. Ma queste versioni probabilmente sono solo leggende metropolitane.
Molto probabilmente, il nome del ponte deriva dalla parola "hon", che significa beffa (scherno). Con la costruzione di questo ponte, gli abitanti dell'isola di Kneiphof ottennero la via più breve per raggiungere l'isola di Lomse, aggirando il ponte alto, che apparteneva ad Altstadt. Pertanto, divenne, per così dire, una presa in giro della principale delle città di Königsberg: Altshadt. Per questo, gli abitanti dell'Altstadt soprannominarono i Kneiphofites: leccatori di miele.
nel 1882 fu eretto un nuovo ponte metallico sul sito del vecchio Honey Bridge.
Ponte del Miele. Vista sull'isola Kneiphof e sul Duomo
È sopravvissuto fino ad oggi ed è utilizzato principalmente come ponte pedonale, poiché attualmente sull'isola Kneiphof, l'attrazione principale della città di Kaliningrad, si trova solo la cattedrale. Al giorno d'oggi, gli sposi appendono alla ringhiera dei lucchetti con i loro nomi e la data del matrimonio. Ponte del Miele, e le chiavi delle serrature vengono rotte e gettate nel fiume Pregel.
Il problema dei sette ponti di Königsberg, Leonhard Euler e la teoria dei grafi
Sin dai tempi antichi gli abitanti di Königsberg si sono scontrati con un enigma: è possibile attraversare tutti i ponti camminando su ciascuno una sola volta? Questo problema è stato risolto sia teoricamente, sulla carta, sia in pratica, durante le passeggiate, passando lungo questi stessi ponti. Nessuno è stato in grado di dimostrare che ciò fosse impossibile, ma nessuno avrebbe potuto fare una passeggiata così “misteriosa” sui ponti.
Nel 1736, il famoso matematico, membro dell'Accademia delle scienze di San Pietroburgo, Leonhard Euler, si impegnò a risolvere il problema dei sette ponti. Nello stesso anno ne scrive all'ingegnere e matematico Marioni. Eulero scrisse di aver trovato una regola secondo la quale non è difficile calcolare se sia possibile attraversare tutti i ponti senza attraversarne nessuno due volte. Sui sette ponti di Königsberg questo è impossibile.
Su un diagramma di città (grafico), i bordi del grafico corrispondono ai ponti e i vertici del grafico (i punti in cui le linee si collegano) corrispondono a parti della città. Riflettendo sul problema, Eulero arrivò alle seguenti conclusioni:
i vertici del grafico possono essere pari o dispari- con un tratto di penna puoi disegnare un grafico, i cui vertici sono tutti pari, puoi iniziare da qualsiasi vertice del grafico e terminare con lo stesso vertice
- il numero di vertici dispari (quelli a cui conduce un numero dispari di spigoli) deve essere dispari; un grafo con un numero pari di vertici dispari non esiste
- È impossibile disegnare un grafico con più di due vertici dispari con un solo tratto.
Il grafico dei ponti di Königsberg ha quattro vertici dispari, cioè tutto. Pertanto, non è possibile attraversare tutti i ponti senza passarne uno due volte.
NOTIZIE DEL FORO  Teoria dei Cavalieri dell'Etere | 23.02.2020 - 19:17: -> - Karim_Khaidarov. 23.02.2020 - 19:14: |
