Problemet med de sju Königsbergsbroarna

Königsbergs broproblem [ 1 ] [ 2 ] [ 3 ] _____  [9] [10] ) är ett gammalt matematiskt problem som frågade hur det är möjligt att korsa alla sju broarna i centrum av det gamla Königsberg utan att gå igenom någon av dem två gånger. Det löstes först i ett papper daterat 1736 [2] [11] av matematikern Leonhard Euler , som bevisade att detta var omöjligt och uppfann Euler-cykler under bevisets gång . Eulers lösning av Königsbergs broproblem var den första tillämpningen någonsin av grafteori , men utan att använda termen " graf " och utan att rita diagram av grafer.   

Historik

I centrum av Königsberg (numera Kaliningrad ) vid floden Pregel (nuvarande Pregolya ) ligger två öar: Kneiphof (nuvarande Immanuel Kant Island) och Lomse (nuvarande Oktyabrsky Island ). På stranden av Pregel norr om ön Kneiphof ligger Altstadt , söder om Vorstadt . Broar byggdes över Pregel som förbinder dessa fyra distrikt [12] . Figuren till höger visar Königsbergs centrum på en karta från 1652 med beteckningarna: A - Altstadt, B - Kneiphof, C - Lomse och D - Vorstadt.

Historien om byggandet av broar i Königsberg

De sju första broarna i Königsbergs centrum, som förbinder Altstadt, Kneiphof, Lomse och Vorstadt, byggdes under de följande åren i följande ordning [12] . Antalet broar i den ordning de byggdes visas i bilden till höger.

1. Butiksbrygga (1286)

Den första bron över Königsberg går tillbaka till 1286. Ansluten Altstadt och Kneiphof. Tillhörde staden Altstadt och gav staden enkel tillgång till marknaderna i Kneiphof [12] .

2. Grön bro (1322)

Den andra bron över Königsberg byggdes 1322. Förbind Kneiphof med Vorstadt och gav enkel tillgång till avlägsna områden. Bron kallades Green på grund av de gröna vågorna som fungerar som bakgrunden till Kneiphofs vapen [12] .

3. Arbetsbro (1377)

På 1300-talet fanns ett slakteri i östra Vorstadt. För att underlätta transporten av kött byggdes en tredje bro mellan Kneiphof och Vorstadt 1377 [12] .

4. Smedens bro (1397)

1397 byggdes den fjärde Smedsbron i den nordöstra delen av Kneiphof, som började nära smedsverkstäderna i Altstadt [12] .

Om en graf ritas över dessa fyra broar , då blir det Euler , det vill säga alla fyra broarna kan förbigås en gång längs en stängd rutt, med start från vilken plats som helst. Invånarna skulle kunna ta sådana promenader [12] .

5. Träbro (1404)

Timmer avverkades på ön Lomse, och en femte bro mellan Altstadt och Lomse, byggd mellan 1400 och 1404, underlättade leveransen av timmer [12] .

6. Hög bro (1506)

Den sjätte bron byggdes 1506 för att förbinda Lomse och Vorstadt [12] .

7. Honungsbron (1542)

Den sjunde av Eulers broar, som förbinder de två öarna, färdigställdes 1542. Den byggdes av invånarna i Kneiphof för att passera till den norra stranden, förbi de två broarna från Kneiphof som kontrolleras av Altstadt. Enligt legenden gav Kneiphof en tunna honung till Altstadt för att få tillstånd att bygga en bro [12] .

Så 1542 var alla sju broarna i Königsberg, som Euler betraktade, på plats. Nu kunde inte invånarna gå förbi alla broar på en gång [12] .

Problemhistorik

Framväxten av grenen av matematikens grafteori är förknippad med matematiska pussel, och under en ganska lång tid var grafteori "frivol" och helt förknippad med spel och underhållning. Detta öde för grafteorin upprepar sannolikhetsteorins öde , som också först hittade sin tillämpning endast i spel [13] .

Invånarna i Koenigsberg spelade ett slags spel: hur man passerar genom alla stadens broar så att rutten inte korsade någon av dem två gånger [3] . "Som jag hörde", skrev Leonhard Euler, "förnekar vissa att detta kan göras, andra tvivlar på det, men ingen bekräftar en sådan möjlighet. [14] »

Publiceringshistorik för Leonhard Eulers tidning

Leonhard Euler, en enastående schweizisk, preussisk och rysk matematiker och mekaniker , akademiker vid St. Petersburgs vetenskapsakademi blev intresserad av detta spel. Historien om publiceringen av den berömda artikeln av Leonhard Euler "Lösningen av ett problem relaterat till positionens geometri", skriven i samband med detta, har följande stadier kända från moderna publikationer:

• först , den 26 augusti  ( 6 september )  1735 [15] presenterade Euler en artikel på konferensen för St. Petersburgs vetenskapsakademi [2] ;
• 1736 skickade Euler, som en del av sin vetenskapliga korrespondens, följande två brev:

• 13 mars  ( 24 ),  1736 - brev till Johann Jacob Marinoni , en österrikisk astronom och matematiker, daterat 13 mars [24], 1736, Petersburg. Detta brev är helt ägnat åt Königsbergs broproblem [16] [17] ;
• 3 april  ( 14 ),  1736 - ett brev till Karl Leonard Gottlieb Oehler , en tysk politiker och astronom, daterat 3 april [14], 1736, Petersburg. I slutet av detta brev talar vi om huvudidéerna i tidningen [16] [18] ;

• 1741 i St Petersburg publicerades Eulers artikel slutligen på latin med datumet 1736 [16] [19] :

Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. S. 128-140.

Översatt [14] :

Leonard Euler. Lösning av ett problem relaterat till positionsgeometri / Proceedings of the St. Petersburg Academy of Sciences. 8 (1736). 1741, s. 128-140.

Eftersom publiceringen av Leonhard Eulers artikel "Lösningen av ett problem relaterat till positionens geometri" är daterad 1736, och båda bokstäverna som nämns ovan är från detta år, är detta år utsett av världens matematiska samfund som födelsedatumet för avsnitt av matematik grafteorin [2] .

En modern lösning på problemet

Problemformulering

Problemet med Königsbergsbroar formuleras olika av olika författare.

1. Rutten är godtycklig

I samband med dessa broar ställdes frågan om det är möjligt att gå över dem på ett sådant sätt att man passerar var och en av dessa broar och exakt en gång.

— Leonhard Euler. Lösning av ett problem relaterat till positionsgeometri [14]

För invånarna i Königsberg fanns det ett slags spel: att hitta en sådan väg för att gå runt i staden som skulle passera genom var och en av broarna som visas i figuren exakt en gång.

— Fritsch R. et al. Selected Chapters in Graph Theory [3]

2. Rutten måste stängas

Uppgiften var följande: att hitta en väg för att passera alla fyra delarna av landet, som skulle börja med någon av dem, sluta på samma del och passera exakt en gång över varje bro.

— Frank Harari. Grafteori [1]

3. Slingvägar måste börja i alla delar av staden

Faktum är att det krävs att hitta fyra vägar som går förbi Königsbergsbroarna, med start i fyra delar av staden.

Frågan var, är det möjligt att göra en promenad på ett sådant sätt att man, efter att ha lämnat huset, kommer tillbaka och passerar exakt en gång över varje bro?

— Ore O. Graphs och deras tillämpningar [20]

Bygga en uppgiftsgraf

Den moderna lösningen av problemet med Königsberg-broar börjar med konstruktionen av en graf över problemet (se figuren till höger) [21] :

• topparna på grafen är fyra delar av Königsbergs centrum, i vilka staden är uppdelad av två grenar och en flodkanal;
• grafens revben är de sju broarna i centrum av staden;
• kanternas ändspetsar är delar av Königsbergs centrum förbundna med dessa broar.

Königsberg-bronproblemet kan omformuleras i termer av grafteori enligt följande [22] :

• Har grafen för Königsberg-bronproblemet en Euler-cykel eller åtminstone en Euler-kedja ?

Eulers satser

Låt oss börja med definitioner, gå vidare till satser och avsluta med följder [22] :

• Eulerkedja - en sekvens av kanter (angränsande kanter har en gemensam vertex) som går förbi alla kanter på grafen en gång;
• Euler-cykeln är en sluten Euler-kedja.

Följande två satser dök först upp i Leonhard Eulers artikel om Königsbergs broar [22] :

• Eulers första sats, 1736. En graf med två eller flera hörn har en Eulercykel om och bara om varje hörn har ett jämnt antal kanter;
• Eulers andra teorem, 1736. En graf med två eller flera hörn har en unik Euler-bana om och bara om exakt två hörn har ett udda antal kanter.

Tre konsekvenser kan härledas från dessa två satser [22] :

• om en graf med två hörn som innehåller ett udda antal kanter har en Euler-kedja, då är dessa två hörn kedjans initiala och sista hörn;
• en graf med två eller flera hörn har en Euler-kedja om och endast om antingen varje hörn har ett jämnt antal kanter eller exakt två hörn har ett udda antal kanter;
• Königsbergsbronproblemet har ingen lösning, eftersom fyra hörn i grafen för detta problem har en udda grad.

Lösning av problemet enligt Leonhard Euler

Problemformulering

Leonhard Euler formulerade i sin berömda artikel problemet med sju Königsberg-broar enligt följande [14] :

2. Denna uppgift, fick jag veta, är ganska välkänd och är relaterad till detta. I staden Königsberg, i Preussen, finns en ö som heter Kneiphof ; floden som omger den är uppdelad i två grenar, vilket kan ses på figuren. Denna flods grenar korsas av sju broar a , b , c , d , e , f och g . I samband med dessa broar ställdes frågan om det är möjligt att gå över dem på ett sådant sätt att man passerar var och en av dessa broar och exakt en gång.

— Leonhard Euler. Lösa ett problem relaterat till positionsgeometri

Lösning på problemet

Leonhard Euler formulerade sin metod enligt följande (se figuren ovan) [23] :

4. Hela min metod bygger på rätt notation för broarnas individuella passager. Jag använder de stora bokstäverna A, B, C, D för att ange de enskilda områden som floden delar landet i. Alltså, om någon flyttar från område A till område B över en bro a eller b, så betecknar jag passagen av bron med symbolen AB.

— Leonhard Euler. Lösa ett problem relaterat till positionsgeometri

I modernt språk betyder det att grafen över stadens broar motsvarar grafen, som är:

• fyra toppar enligt beteckningarna för de fyra delarna av stadskärnan;
• topparna är förbundna med sju kanter-broar enligt beteckningarna för sju broar.

En ganska modern och enkel lösning av Leonhard Euler på problemet med Königsbergsbron är följande. Man bör bara komma ihåg att Euler inte kände till modern terminologi, inte använde termen "graf", kallad kanten "bro", och vertex - "area" eller "bokstav" och inte ritade moderna bilder av grafer [23] .

• "Därför blir det uppenbart att om det är möjligt att passera över sju broar, och var och en av dem exakt en gång, så kommer denna väg att representeras av åtta bokstäver."
• ”... Jag har utvecklat en regel genom vilken man lätt kan avgöra - både för detta problem och för alla liknande problem - om en sådan ordning av bokstäver kan genomföras.

“ 8. För att härleda en sådan regel överväger jag ett specifikt område dit ett godtyckligt antal broar kan leda , etc. Från dessa broar kommer jag först att överväga en specifik bro som leder till området . Om en resenär korsar den här bron, var de antingen i området innan de korsade den här bron, eller så kommer de att vara i området efter det. Därför, för att beteckna denna passage över bron, som beskrivits ovan, är det nödvändigt att bokstaven visas en gång .

• "Om tre broar leder till området, till exempel , och resenären passerar genom alla tre broarna, kommer bokstaven att visas i beskrivningen av hans rörelse på broarna två gånger, oavsett om hans rutt startade från eller inte. På samma sätt, om det finns fem broar som leder till området, bör bokstaven visas tre gånger när den beskriver dess rörelse. Och när antalet broar är ett godtyckligt udda tal, om du ökar det med en, visar hälften av det resulterande talet hur många gånger bokstaven måste förekomma .
• “ 9. Därför är det i fallet med Königsbergsbroarna, eftersom fem broar leder till ön , nödvändigt att bokstaven förekommer i beskrivningen av rörelsen längs dessa broar tre gånger. Dessutom måste brevet mötas två gånger , eftersom det finns tre broar som leder till området, och bokstäverna måste mötas två gånger vardera. Därför, i en sekvens av åtta bokstäver som beskriver rutten i fråga, som passerar genom sju broar, måste bokstaven förekomma tre gånger och var och en av bokstäverna två gånger. Detta kan dock inte vara i en sekvens av åtta bokstäver. Därför är det tydligt att en sådan promenad längs Königsbergs sju broar är omöjlig.”

Generalisering av lösningen av problemet

Leonhard Euler löste problemet i allmänna termer och bevisade på vägen att för vilken graf som helst är antalet hörn med ett udda antal kanter jämnt [24] :

• "Jag kommer först att notera att alla antal broar" som leder in i regionen, "tillsammans ger dubbelt så många broar som alla broar. Anledningen är att varje bro räknas två gånger i denna räkning så att alla broar som leder in i ett givet område räknas, för varje bro leder in i de två områden som den förbinder.

17. Av denna observation följer att summan [av talen] av alla broar som leder till varje region är ett jämnt tal, eftersom hälften av denna summa är exakt antalet broar. Därför kan det inte hända att bland antalet broar som leder till något område är exakt en udda; det kan inte heller hända att det finns tre, fem, etc. med udda tal. Därför, om antalet broar" som leder till regionen "är udda tal, är deras summa jämn."

I slutet av artikeln skrev Leonhard Euler ner de allmänna slutsatserna för vilken graf som helst på ett ganska modernt språk [24] :

20. Följande regel gör det därför i alla möjliga fall möjligt att direkt och utan svårighet ta reda på om det är möjligt att genomföra en promenad över alla broar utan upprepning:

Om det finns fler än två områden dit ett udda antal broar leder kan man med säkerhet säga att en sådan promenad är omöjlig.

Om det däremot bara finns två regioner som ett udda antal broar leder till, är vandringen genomförbar, förutsatt att den börjar i en av dessa två regioner.

Om det slutligen inte finns något område dit ett udda antal broar leder, är en promenad med de nödvändiga förutsättningarna möjlig och den kan börja i vilket område som helst.

Därför, med hjälp av denna regel, kan problemet lösas helt.

— Leonhard Euler. Lösa ett problem relaterat till positionsgeometri

Se även

• Problemet med riddarens drag
• grafteori
• Euler cykel
• Topologi
• Kaliningrads broar
• Problemet med resande säljare

Anteckningar

1. ↑ 1 2 Harari Frank. Graph Theory, 2003 , sid. 13.
2. ↑ 1 2 3 4 Fleischner G. Euler grafer och relaterade frågor, 2002 , sid. elva.
3. ↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of graph theory, 2008 , sid. ett.
4. ↑ Fleischner G. Euler grafer och relaterade frågor, 2002 , sid. 17.
5. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 , sid. 129.
6. ↑ Frank Harary Graph Theory, 2007 , s. ett.
7. ↑ Königsberg broproblem // Britannica .
8. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of graph theory, 2008 , sid. vii.
9. ↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , sid. 24.
10. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of graph theory, 2008 , sid. ix.
11. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of graph theory, 2008 , sid. 151.
12. ↑ 1 2 3 4 5 6 7 8 9 10 11 Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg, 2007 .
13. ↑ Ore O. Graphs and their application, 1965 , sid. 6.
14. ↑ 1 2 3 4 Fleischner G. Euler grafer och relaterade frågor, 2002 , sid. 26.
15. ↑ Protokoll från mötena för den kejserliga vetenskapsakademiens konferens från 1725 till 1803. Volym I. 1725-1743, 1897 , sid. 220-221.
16. ↑ 1 2 3 Fleischner G. Euler grafer och relaterade frågor, 2002 , sid. femton.
17. ↑ Letters to scientists, 1963 , sid. 152-158.
18. ↑ Letters to scientists, 1963 , sid. 330-353.
19. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 .
20. ↑ Ore O. Graphs and their application, 1965 , sid. 33.
21. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of graph theory, 2008 , sid. fyra.
22. ↑ 1 2 3 4 Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of graph theory, 2008 , sid. 8-12.
23. ↑ 1 2 Fleischner G. Euler grafer och relaterade frågor, 2002 , sid. 27-28.
24. ↑ 1 2 Fleischner G. Euler grafer och relaterade frågor, 2002 , sid. 31-32.

Litteratur

• Ore O. Grafer och deras tillämpning / Per. från engelska. L. I. Golovina. Ed. I. M. Yagloma. M.: Mir, 1965. 174 s.: ill.
• Protokoll från mötena för den kejserliga vetenskapsakademins konferens från 1725 till 1803. Volym I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. St Petersburg: IAN Printing House, 1897. 883 sid.
• Harary Frank. Grafteori / Per. från engelska. V. P. Kozyreva. Ed. G.P. Gavrilova. 2:a upplagan. M.: Redaktionell URSS, 2003. 296 s.: ill. ISBN 5-354-00301-6 .
• Fleishner G. Euler grafer och relaterade frågor. M.: Mir, 2002. 335 s.: ill. ISBN 5-03-003115-4 (ryska). ISBN 0-444-88395-9 . [Fleischner H. Eulerian grafer och relaterade ämnen. P. 1, V. 1. Amsterdam: North-Holland, 1990.]
• Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of Graph Theory: Textbook / Per. med honom. E.E. Pereguda; Paul ed. S. V. Matsievsky. Kaliningrad: Ryska statsuniversitetets förlag. I. Kant, 2008. 192 s.: ill. ISBN 978-5-88874-880-0 .
• Leonard Euler. Brev till forskare / Ed. Akademiker V. I. Smirnov . - Moscow-Leningrad: Publishing House of the Academy of Sciences of the USSR , 1963. Innehåller den latinska originaltexten av brev och översättning till ryska av Yu. Kh. Kopelevich (brev till Marinoni) och T. A. Lukina (brev till Eler).
• Konigsbergsbroproblem // Britannica. * Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Petropolitanae. 8 (1736) 1741, 128–140.
• Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg–A Historical Perspective // ​​Networks. 2007. 49(3):199–203.
• Frank Hararys grafteori. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283 sid.
• Denes Konig. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft MBH, 1936.

Ordböcker och uppslagsverk	Stor dansk Britannica (online)