Problemet med de syv Königsberg-broer

Königsberg - broproblemet [ 1 ] [ 2 ] [ 3 ] _____  [9] [10] ) er et gammelt matematisk problem, der spurgte, hvordan det er muligt at krydse alle syv broer i centrum af det gamle Königsberg uden at gå igennem nogen af ​​dem to gange. Det blev først løst i et papir dateret 1736 [2] [11] af matematikeren Leonhard Euler , som beviste, at dette var umuligt og opfandt Euler-cyklusser i løbet af beviset . Eulers løsning af Königsberg-broproblemet var den første nogensinde anvendelse af grafteori , men uden at bruge udtrykket " graf " og uden at tegne diagrammer af grafer.   

Historie

I centrum af Königsberg (nu Kaliningrad ) ved Pregel-floden (nu Pregolya ) ligger to øer: Kneiphof (nu Immanuel Kant Island) og Lomse (nu Oktyabrsky Island ). På bredden af ​​Pregel nord for øen Kneiphof ligger Altstadt , mod syd - Vorstadt . Broer blev bygget over Pregel, der forbinder disse fire distrikter [12] . Figuren til højre viser centrum af Königsberg på et kort fra 1652 med betegnelserne: A - Altstadt, B - Kneiphof, C - Lomse og D - Vorstadt.

Historien om byggeriet af broer i Königsberg

De syv første broer i centrum af Königsberg, der forbinder Altstadt, Kneiphof, Lomse og Vorstadt, blev bygget i de følgende år i følgende rækkefølge [12] . Antallet af broer i den rækkefølge, de blev bygget, er vist på figuren til højre.

1. Butiksbro (1286)

Königsbergs første bro går tilbage til 1286. Forbundet Altstadt og Kneiphof. Tilhørte byen Altstadt og gav byen let adgang til markederne i Kneiphof [12] .

2. Grøn bro (1322)

Den anden bro i Königsberg blev bygget i 1322. Forbundet Kneiphof med Vorstadt og gav nem adgang til fjerntliggende områder. Broen blev kaldt Grøn på grund af de grønne bølger, der tjener som baggrund for Kneiphof-våbenskjoldet [12] .

3. Arbejdsbro (1377)

I det 14. århundrede lå der et slagteri i den østlige del af Vorstadt. For at lette transporten af ​​kød blev der i 1377 bygget en tredje bro mellem Kneiphof og Vorstadt [12] .

4. Smedebro (1397)

i 1397 blev den fjerde Smedebro bygget i den nordøstlige del af Kneiphof, som begyndte nær smedeværkstederne i Altstadt [12] .

Hvis der tegnes en graf over disse fire broer , så vil det være Euler , det vil sige, at alle fire broer kan omgås én gang langs en lukket rute, startende fra et hvilket som helst sted. Beboere kunne tage sådanne gåture [12] .

5. Træbro (1404)

Der blev høstet tømmer på øen Lomse, og en femte bro mellem Altstadt og Lomse, bygget mellem 1400 og 1404, lettede leveringen af ​​tømmer [12] .

6. Højbro (1506)

Den sjette bro blev bygget i 1506 for at forbinde Lomse og Vorstadt [12] .

7. Honningbro (1542)

Den syvende af Eulers broer, der forbinder de to øer, stod færdig i 1542. Det blev bygget af indbyggerne i Kneiphof for at passere til den nordlige bred, uden om de to broer fra Kneiphof kontrolleret af Altstadt. Ifølge legenden gav Kneiphof en tønde honning til Altstadt for at få tilladelse til at bygge en bro [12] .

Så i 1542 var alle syv broer i Königsberg, betragtet af Euler, på plads. Nu kunne indbyggerne ikke omgå alle broer på én gang [12] .

Problemhistorie

Fremkomsten af ​​grenen af ​​matematisk grafteori er forbundet med matematiske gåder, og for nogle ret lang tid var grafteori "letfærdig" og helt forbundet med spil og underholdning. Denne skæbne for grafteori gentager skæbnen for sandsynlighedsteori , som også først fandt sin anvendelse kun i gambling [13] .

Indbyggerne i Koenigsberg spillede en slags leg: hvordan man passerer gennem alle byens broer, så ruten ikke krydsede nogen af ​​dem to gange [3] . "Som jeg hørte," skrev Leonhard Euler, "nægter nogle, at dette kan lade sig gøre, andre tvivler på det, men ingen bekræfter en sådan mulighed. [14] »

Udgivelseshistorie for Leonhard Eulers papir

Leonhard Euler, en fremragende schweizisk, preussisk og russisk matematiker og mekaniker , akademiker ved St. Petersburg Academy of Sciences blev interesseret i dette spil. Historien om offentliggørelsen af ​​den berømte artikel af Leonhard Euler "Løsningen af ​​et problem relateret til positionens geometri", skrevet i forbindelse med dette, har følgende stadier kendt fra moderne publikationer:

• først , den 26. august  ( 6. september )  1735 [15] præsenterede Euler en artikel på konferencen for St. Petersburgs Videnskabsakademi [2] ;
• derefter i 1736 sendte Euler, som en del af sin videnskabelige korrespondance, følgende to breve:

• 13. marts  ( 24 ),  1736 - brev til Johann Jacob Marinoni , en østrigsk astronom og matematiker, dateret 13. marts [24], 1736, Petersborg. Dette brev er udelukkende viet Königsberg-broproblemet [16] [17] ;
• 3. april  ( 14 ),  1736 - et brev til Karl Leonard Gottlieb Oehler , en tysk politiker og astronom, dateret 3. april [14], 1736, Petersborg. I slutningen af ​​dette brev taler vi om hovedideerne i papiret [16] [18] ;

• i 1741 i St. Petersborg blev Eulers artikel endelig udgivet på latin med datoen 1736 [16] [19] :

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

Oversat [14] :

Leonard Euler. Løsning af et problem relateret til positionsgeometri / Proceedings of the St. Petersburg Academy of Sciences. 8 (1736). 1741, s. 128-140.

Da udgivelsen af ​​Leonhard Eulers artikel "Løsningen af ​​et problem relateret til positionens geometri" er dateret 1736, og begge ovennævnte bogstaver stammer fra dette år, er dette år udpeget af verdens matematiske samfund som fødselsdatoen for afsnit af matematik grafteori [2] .

En moderne løsning på problemet

Problemformulering

Problemet med Königsberg-broer er formuleret forskelligt af forskellige forfattere.

1. Ruten er vilkårlig

I forbindelse med disse broer blev der rejst spørgsmålet, om det er muligt at gå over dem på en sådan måde, at man passerer over hver af disse broer, og præcis én gang.

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri [14]

For indbyggerne i Königsberg var der en slags leg: at finde en sådan rute til at gå rundt i byen, der ville passere gennem hver af broerne vist på figuren præcis én gang.

— Fritsch R. et al. Udvalgte kapitler i grafteori [3]

2. Ruten skal lukkes

Opgaven var som følger: at finde en rute til at passere gennem alle fire dele af landet, som ville begynde med en hvilken som helst af dem, ende på den samme del og passere præcis én gang over hver bro.

- Frank Harari. Grafteori [1]

3. Loop-ruter skal starte i alle dele af byen

Faktisk er det nødvendigt at finde fire ruter uden om Königsberg-broerne, startende i fire dele af byen.

Spørgsmålet var, om det er muligt at gå en tur på en sådan måde, at man, efter at have forladt huset, kommer tilbage og passerer præcis én gang over hver bro?

— Ore O. Graphs og deres anvendelser [20]

Opbygning af en opgavegraf

Den moderne løsning af problemet med Königsberg-broer begynder med konstruktionen af ​​en graf over problemet (se figuren til højre) [21] :

• toppene af grafen er fire dele af centrum af Königsberg, hvor byen er opdelt af to grene og en flodkanal;
• grafens ribber er de syv broer i centrum af byen;
• kanternes endespidser er dele af Königsbergs centrum forbundet med disse broer.

Königsberg-broproblemet kan omformuleres i form af grafteori som følger [22] :

• Har grafen for Königsberg-broproblemet en Euler-cyklus eller i det mindste en Euler-kæde ?

Eulers sætninger

Lad os starte med definitioner, gå videre til sætninger og slutte med følger [22] :

• Euler-kæde - en sekvens af kanter (nabokanter har et fælles toppunkt), der omgår alle grafens kanter én gang;
• Euler-cyklus er en lukket Euler-kæde.

De følgende to sætninger dukkede først op i Leonhard Eulers papir om Königsberg-broer [22] :

• Eulers første sætning, 1736. En graf med to eller flere hjørner har en Euler-cyklus, hvis og kun hvis hvert hjørne har et lige antal kanter;
• Eulers anden sætning, 1736. En graf med to eller flere hjørner har en unik Euler-sti, hvis og kun hvis præcis to hjørner har et ulige antal kanter.

Tre konsekvenser kan udledes af disse to teoremer [22] :

• hvis en graf med to hjørner, der indeholder et ulige antal kanter, har en Euler-kæde, så er disse to knudepunkter kædens indledende og sidste spidser;
• en graf med to eller flere hjørner har en Euler-kæde, hvis og kun hvis enten hvert hjørne har et lige antal kanter, eller nøjagtigt to hjørner har et ulige antal kanter;
• Königsberg-broproblemet har ingen løsning, da fire hjørner i grafen for dette problem har en ulige grad.

Løsning af problemet ifølge Leonhard Euler

Problemformulering

Leonhard Euler formulerede i sin berømte artikel problemet med syv Königsberg-broer som følger [14] :

2. Denne opgave, fik jeg at vide, er ret velkendt og er relateret til denne. I byen Königsberg i Preussen er der en ø, der hedder Kneiphof ; floden der omgiver den er delt i to grene, hvilket kan ses på figuren. Denne flods grene krydses af syv broer a , b , c , d , e , f og g . I forbindelse med disse broer blev der rejst spørgsmålet, om det er muligt at gå over dem på en sådan måde, at man passerer over hver af disse broer, og præcis én gang.

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri

Løsning af problemet

Leonhard Euler formulerede sin metode som følger (se figuren ovenfor) [23] :

4. Hele min metode er baseret på den rette notation for broernes enkelte passager. Jeg bruger de store bogstaver A, B, C, D til at angive de enkelte områder, som åen deler landet i. Således, hvis nogen bevæger sig fra område A til område B over en bro a eller b, så betegner jeg broens passage med symbolet AB.

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri

I moderne sprog betyder det, at grafen over byens broer svarer til grafen, som er:

• fire toppe ifølge betegnelserne for de fire dele af bymidten;
• hjørnerne er forbundet med syv kanter-broer i henhold til betegnelserne for syv broer.

En ret moderne og enkel løsning af Leonhard Euler af Königsberg-broproblemet er som følger. Det skal kun huskes på, at Euler ikke kendte moderne terminologi, ikke brugte udtrykket "graf", kaldet kanten "bro", og toppunktet - "areal" eller "bogstav" og ikke tegnede moderne billeder af grafer [23] .

• "Således bliver det indlysende, at hvis det er muligt at passere over syv broer, og hver af dem præcis én gang, så vil denne rute blive repræsenteret med otte bogstaver."
• “... jeg har udviklet en regel, hvorefter man let kan afgøre - både for dette problem og for alle lignende problemer - om en sådan ordning af bogstaver kan gennemføres.

“ 8. For at udlede en sådan regel, overvejer jeg et bestemt område , som et vilkårligt antal broer kan føre ind i osv. Ud fra disse broer vil jeg først overveje en bestemt bro, der fører til området . Hvis en rejsende krydser denne bro, var de enten i området, før de krydsede denne bro, eller også vil de være i området efter det. For at udpege denne passage over broen, som beskrevet ovenfor, er det derfor nødvendigt, at bogstavet vises én gang .

• "Hvis tre broer fører til området, for eksempel , og den rejsende passerer gennem alle tre broer, så vil bogstavet optræde i beskrivelsen af ​​hans bevægelse på broerne to gange, uanset om hans rute startede fra eller ej. På samme måde, hvis der er fem broer, der fører til området, skal bogstavet vises tre gange, når det beskriver dets bevægelse. Og når antallet af broer er et vilkårligt ulige tal, så hvis du øger det med én, viser halvdelen af ​​det resulterende tal, hvor mange gange bogstavet skal forekomme .
• “ 9. Derfor er det i tilfældet med Königsberg-broerne, da fem broer fører til øen , nødvendigt, at bogstavet forekommer i beskrivelsen af ​​bevægelsen langs disse broer tre gange. Derudover skal brevet mødes to gange , da der er tre broer, der fører til området, og bogstaverne skal mødes to gange hver. Derfor, i en sekvens på otte bogstaver, der beskriver den pågældende rute, der passerer gennem syv broer, skal bogstavet forekomme tre gange, og hvert af bogstaverne to gange. Dette kan dog ikke være i en rækkefølge på otte bogstaver. Det er således klart, at sådan en gåtur langs Königsbergs syv broer er umulig."

Generalisering af løsningen af ​​problemet

Ved at løse problemet i generelle vendinger beviste Leonhard Euler undervejs, at for enhver graf er antallet af hjørner med et ulige antal kanter lige [24] :

• "Jeg vil først bemærke, at alle antallet af broer", der fører ind i regionen, "lagt sammen giver det dobbelte af antallet af alle broer. Årsagen er, at hver bro tælles to gange i denne optælling, således at alle broer, der fører ind i et givet område, tælles, for hver bro fører ind i de to områder, den forbinder.

17. Af denne observation følger det, at summen [af tallene] af alle broer, der fører til hver region, er et lige tal, eftersom halvdelen af ​​denne sum er nøjagtig antallet af broer. Derfor kan det ikke ske, at der blandt antallet af broer, der fører til et hvilket som helst område, er præcis én ulige; det kan heller ikke ske, at der er tre, fem osv. ulige tal. Derfor, hvis antallet af broer, der fører til regionen, "er ulige tal, er deres sum lige."

I slutningen af ​​artiklen skrev Leonhard Euler de generelle konklusioner ned for enhver graf i et ret moderne sprog [24] :

20. Følgende regel gør det derfor i alle mulige tilfælde muligt direkte og uden besvær at finde ud af, om det er muligt at gennemføre en tur over alle broerne uden gentagelser:

Hvis der er mere end to områder, hvortil et ulige antal broer fører, kan man med sikkerhed sige, at en sådan gåtur er umulig.

Hvis der dog kun er to regioner, hvortil et ulige antal broer fører, så er vandringen mulig, forudsat at den starter i en af ​​disse to regioner.

Hvis der endelig ikke er et område, hvortil et ulige antal broer fører, er en gåtur med de nødvendige forhold mulig, og den kan starte i ethvert område.

Derfor kan det stillede problem ved hjælp af denne regel løses fuldstændigt.

- Leonhard Euler. Løsning af et problem relateret til positionsgeometri

Se også

• Problemet med ridderens træk
• grafteori
• Euler cyklus
• Topologi
• Kaliningrads broer
• Problemet med den rejsende sælger

Noter

1. ↑ 1 2 Harari Frank. Graph Theory, 2003 , s. 13.
2. ↑ 1 2 3 4 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. elleve.
3. ↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. en.
4. ↑ Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 17.
5. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 , s. 129.
6. ↑ Frank Harary Graph Theory, 2007 , s. en.
7. ↑ Königsberg-broproblemet // Britannica .
8. ↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. vii.
9. ↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24.
10. ↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. ix.
11. ↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 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 , s. 6.
14. ↑ 1 2 3 4 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 26.
15. ↑ Referater fra møderne i konferencen for det kejserlige videnskabsakademi fra 1725 til 1803. Bind I. 1725-1743, 1897 , s. 220-221.
16. ↑ 1 2 3 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. femten.
17. ↑ Letters to scientists, 1963 , s. 152-158.
18. ↑ Letters to scientists, 1963 , s. 330-353.
19. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 .
20. ↑ Ore O. Graphs and their application, 1965 , s. 33.
21. ↑ Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. fire.
22. ↑ 1 2 3 4 Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler af grafteori, 2008 , s. 8-12.
23. ↑ 1 2 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 27-28.
24. ↑ 1 2 Fleischner G. Euler-grafer og relaterede spørgsmål, 2002 , s. 31-32.

Litteratur

• Ore O. Grafer og deres anvendelse / Pr. fra engelsk. L. I. Golovina. Ed. I. M. Yagloma. M.: Mir, 1965. 174 s.: ill.
• Referater fra møderne i konferencen for det kejserlige videnskabsakademi fra 1725 til 1803. Bind I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Petersborg: IAN trykkeri, 1897. 883 s.
• Harary Frank. Grafteori / Pr. fra engelsk. V. P. Kozyreva. Ed. G. P. Gavrilova. 2. udgave. M.: Redaktionel URSS, 2003. 296 s.: ill. ISBN 5-354-00301-6 .
• Fleishner G. Euler grafer og relaterede spørgsmål. M.: Mir, 2002. 335 s.: ill. ISBN 5-03-003115-4 (russisk). ISBN 0-444-88395-9 . [Fleischner H. Eulerske grafer og beslægtede emner. S. 1, V. 1. Amsterdam: North-Holland, 1990.]
• Frich R., Peregud E. E., Matsievsky S. V. Udvalgte kapitler i grafteori: Lærebog / Per. med ham. E. E. Pereguda; Paul udg. S. V. Matsievsky. Kaliningrad: Forlaget for det russiske statsuniversitet. I. Kant, 2008. 192 s.: ill. ISBN 978-5-88874-880-0 .
• Leonard Euler. Breve til videnskabsmænd / Ed. Akademiker V. I. Smirnov . - Moscow-Leningrad: Publishing House of the Academy of Sciences of the USSR , 1963. Indeholder den originale latinske tekst af breve og oversættelse til russisk af Yu. Kh. Kopelevich (brev til Marinoni) og T. A. Lukina (brev til Eler).
• Konigsberg-broproblem // 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 Harary grafteori. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283 s.
• Denes Konig. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft MBH, 1936.

Ordbøger og encyklopædier	Flot dansk Britannica (online)