A hét königsbergi híd probléma

A königsbergi hidak probléma [ 1 ] [ 2 ] [ 3 ] _____  [9] [10] ) egy régi matematikai probléma, amely azt kérdezte, hogyan lehet átkelni mind a hét hídon a város közepén. a régi Königsberg anélkül, hogy kétszer áthaladt volna valamelyiken. Ezt először egy matematikus egy 1736 -os cikkében [2] [11] oldotta meg.  Leonhard Euler , aki bebizonyította, hogy ez lehetetlen, és a bizonyítás során feltalálta az Euler-ciklusokat . A königsbergi hídprobléma Euler-féle megoldása volt a gráfelmélet első alkalmazása , de a „ gráf ” kifejezés használata és a gráfok diagramjainak megrajzolása nélkül.

Történelem

Königsberg (ma Kalinyingrád ) központjában a Pregel folyón (ma Pregolya ) két sziget található: Kneiphof (ma Immanuel Kant-sziget) és Lomse (ma Oktyabrsky-sziget ). A Pregel partján, Kneiphof szigetétől északra található Altstadt , délre Vorstadt . A négy kerületet összekötő Pregelen hidakat építettek [12] . A jobb oldali ábra Königsberg központját mutatja egy 1652-es térképen a következő jelölésekkel: A - Altstadt, B - Kneiphof, C - Lomse és D - Vorstadt.

A königsbergi hidak építésének története

Königsberg központjának hét első hídja, amely Altstadtot, Kneiphofot, Lomsét és Vorstadtot köti össze, a következő években épült a következő sorrendben [12] . A hidak számát építésük sorrendjében a jobb oldali ábra mutatja.

1. Bolthíd (1286)

Königsberg első hídja 1286-ból származik. Összekötötte Altstadtot és Kneiphofot. Altstadt városához tartozott, és könnyű hozzáférést biztosított a városnak Kneiphof piacaihoz [12] .

2. Zöld híd (1322)

Königsberg második hídja 1322-ben épült. Összekötötte Kneiphofot Vorstadttal, és könnyű hozzáférést biztosított a távoli területekhez. A hidat a Kneiphof címer háttereként szolgáló zöld hullámok miatt nevezték el Zöldnek [12] .

3. Munkahíd (1377)

A 14. században Vorstadt keleti részén vágóhíd működött. A hússzállítás megkönnyítésére 1377-ben egy harmadik hidat építettek Kneiphof és Vorstadt között [12] .

4. Kovácshíd (1397)

1397-ben Kneiphof északkeleti részén felépült a negyedik Kovácshíd, amely az altstadti kovácsműhelyek közelében kezdődött [12] .

Ha e négy hídra rajzolunk egy grafikont , akkor az Euler lesz , vagyis mind a négy híd egyszer megkerülhető egy zárt útvonalon, bármely helyről indulva. A lakók tehettek ilyen sétákat [12] .

5. Fahíd (1404)

A fát Lomse szigetén állították ki, és az 1400 és 1404 között épült ötödik híd Altstadt és Lomse között megkönnyítette a fa szállítását [12] .

6. High Bridge (1506)

A hatodik hidat 1506-ban építették Lomse és Vorstadt összekötésére [12] .

7. Honey Bridge (1542)

A két szigetet összekötő hetedik Euler-híd 1542-ben készült el. Kneiphof lakosai építették, hogy az Altstadt által ellenőrzött két Kneiphof hidat megkerülve az északi partra menjenek. A legenda szerint Kneiphof egy hordó mézet adott Altstadtnak, hogy engedélyt kapjon hídépítésre [12] .

Így 1542-ben Königsberg mind a hét hídja, Euler szerint, a helyén volt. Most a lakosok nem tudták egyszerre megkerülni az összes hidat [12] .

Problématörténet

A matematika gráfelmélet ágának megjelenése a matematikai rejtvényekhez kötődik, és a gráfelmélet sokáig „komolytalan” volt, és teljes mértékben a játékokkal és a szórakoztatással kapcsolatos. A gráfelméletnek ez a sorsa megismétli a valószínűségszámítás sorsát , amely szintén először csak a szerencsejátékban talált alkalmazásra [13] .

Koenigsberg lakói egyfajta játékot játszottak: hogyan kell átmenni a város összes hídján úgy, hogy az útvonal egyiket se keresztezze kétszer [3] . „Ahogy hallottam – írta Leonhard Euler –, egyesek tagadják, hogy ez megtörténhet, mások kételkednek benne, de senki sem erősíti meg ezt a lehetőséget. [14] »

Leonhard Euler dolgozatának megjelenési története

Leonhard Euler, a kiváló svájci, porosz és orosz matematikus és mechanikus , a Szentpétervári Tudományos Akadémia akadémikusa érdeklődött a játék iránt. Leonhard Euler "A helyzet geometriájával kapcsolatos probléma megoldása" című, ezzel kapcsolatban írt híres cikkének megjelenésének története a következő, a modern publikációkból ismert szakaszokat tartalmazza:

• először 1735. augusztus 26-án  ( szeptember 6. )  [15] Euler a Szentpétervári Tudományos Akadémia konferenciáján mutatott be egy cikket [2] ;
• majd 1736-ban Euler tudományos levelezésének részeként a következő két levelet küldte:

• 1736. március 13.  ( 24 )  - levél Johann Jacob Marinoni osztrák csillagásznak és matematikusnak, 1736. március 13-án [24], Péterváron. Ez a levél teljes egészében a königsbergi hídproblémának szól [16] [17] ;
• 1736. április 3.  ( 14 )  - levél Karl Leonard Gottlieb Oehler német politikusnak és csillagásznak, 1736. április 3-án [14], Péterváron. E levél végén a dolgozat fő gondolatairól szólunk [16] [18] ;

• 1741-ben Szentpéterváron Euler cikke végül latinul is megjelent 1736-os dátummal [16] [19] :

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

Lefordítva [14] :

Leonard Euler. Egy helyzetgeometriával kapcsolatos probléma megoldása / Proceedings of the St. Petersburg Sciences Academy. 8 (1736). 1741, 128-140.

Mivel Leonhard Euler „A pozíciógeometriával kapcsolatos probléma megoldása” című cikkének megjelenése 1736-ra datálható, és mindkét fent említett levél ebből az évből származik, a matematikai világközösség ezt az évet jelölte meg a világ matematikai közösségének születési dátumaként. a matematika gráfelmélet része [2] .

A probléma modern megoldása

Problémafelvetés

A königsbergi hidak problémáját a különböző szerzők eltérően fogalmazzák meg.

1. Az útvonal tetszőleges

Ezekkel a hidakkal kapcsolatban felvetődött a kérdés, hogy át lehet-e menni rajtuk úgy, hogy mindegyik hídon áthaladjunk, és pontosan egyszer.

– Leonhard Euler. A helyzetgeometriával kapcsolatos egyik probléma megoldása [14]

Königsberg lakosai számára egyfajta játék várt: olyan útvonalat találni a város körüli bejáráshoz, amely az ábrán látható hídon pontosan egyszer halad át.

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

2. Az útvonalat le kell zárni

A feladat a következő volt: meg kell találni a négy földrészen áthaladó útvonalat, amely bármelyikkel kezdődik, ugyanazon a részen ér véget, és minden hídon pontosan egyszer halad át.

– Frank Harari. Gráfelmélet [1]

3. A hurokútvonalaknak minden városrészben el kell indulniuk

Valójában négy, a város négy pontjáról induló, a Königsberg-hidakat elkerülő útvonalat kell találni.

A kérdés az volt, hogy lehet-e úgy sétálni, hogy a ház elhagyása után minden hídon pontosan egyszer haladjunk vissza?

– Ore O. Graphs és alkalmazásaik [20]

Feladatgrafikon készítése

A königsbergi hidak problémájának modern megoldása a probléma grafikonjának felépítésével kezdődik (lásd a jobb oldali ábrát) [21] :

• a grafikon csúcsai Königsberg központjának négy része, amelyre a várost két ág és egy folyócsatorna tagolja;
• a grafikon bordái a hét híd a város központjában;
• az élek végpontjai Königsberg központjának részei, amelyeket ezek a hidak kötnek össze.

A königsbergi hídprobléma gráfelméleti szempontból a következőképpen fogalmazható meg [22] :

• Van-e a Königsberg-híd feladat gráfja Euler-ciklussal vagy legalább Euler-lánccal ?

Euler-tételek

Kezdjük a definíciókkal, folytassuk a tételekkel, és fejezzük be a következményekkel [22] :

• Euler-lánc - élek sorozata (a szomszédos éleknek közös csúcsuk van), amely egyszer megkerüli a gráf összes élét;
• Az Euler-ciklus egy zárt Euler-lánc.

A következő két tétel először Leonhard Euler Königsberg hidakról szóló cikkében jelent meg [22] :

• Euler első tétele, 1736. Egy két vagy több csúcsot tartalmazó gráfnak akkor és csak akkor van Euler-ciklusa, ha minden csúcsnak páros számú éle van;
• Euler második tétele, 1736. Egy két vagy több csúcsot tartalmazó gráfnak akkor és csak akkor van egyedi Euler-útja, ha pontosan két csúcsnak páratlan számú éle van.

Ebből a két tételből három következmény vonható le [22] :

• ha egy páratlan számú élt tartalmazó gráfnak két csúcsa van Euler-lánccal, akkor ez a két csúcs a lánc kezdeti és végső csúcsa;
• egy két vagy több csúcsot tartalmazó gráfnak akkor és csak akkor van Euler-lánca, ha minden csúcsnak páros számú éle van, vagy pontosan két csúcsnak páratlan számú éle van;
• a königsbergi hídfeladatnak nincs megoldása, mivel ennek a feladatnak a gráfjában négy csúcsának páratlan foka van.

A probléma megoldása Leonhard Euler szerint

Problémafelvetés

Leonhard Euler híres cikkében hét königsbergi híd problémáját a következőképpen fogalmazta meg [14] :

2. Azt mondták nekem, hogy ez a feladat meglehetősen ismert, és ehhez kapcsolódik. Königsberg városában, Poroszországban van egy Kneiphof nevű sziget ; az azt körülvevő folyó két ágra oszlik, ami az ábrán is látható. E folyó ágait hét a , b , c , d , e , f és g híd szeli át . Ezekkel a hidakkal kapcsolatban felvetődött a kérdés, hogy át lehet-e menni rajtuk úgy, hogy mindegyik hídon áthaladjunk, és pontosan egyszer.

– Leonhard Euler. Egy pozíciógeometriával kapcsolatos probléma megoldása

A probléma megoldása

Leonhard Euler a következőképpen fogalmazta meg módszerét (lásd a fenti ábrát) [23] :

4. Az egész módszerem a hidak egyes átjáróinak megfelelő jelölésén alapul. A nagybetűkkel A, B, C, D jelzem azokat az egyes területeket, amelyekre a folyó felosztja a földet. Így ha valaki egy a vagy b hídon át A területről B területre mozog, akkor a híd áthaladását az AB szimbólummal jelölöm.

– Leonhard Euler. Egy pozíciógeometriával kapcsolatos probléma megoldása

A mai nyelven ez azt jelenti, hogy a város hídjainak grafikonja megfelel a grafikonnak, amely a következő:

• négy csúcs a városközpont négy részének kijelölése szerint;
• a csúcsokat hét él-híd köti össze hét híd megjelölése szerint.

Leonhard Euler meglehetősen modern és egyszerű megoldása a königsbergi híd problémájára a következő. Csak azt kell szem előtt tartani, hogy Euler nem ismerte a modern terminológiát, nem használta a "gráf" kifejezést, amelyet élnek "hídnak" neveztek, és a csúcsot - "terület" vagy "betű", és nem rajzolt modern képeket a gráfokról. [23] .

• „Így nyilvánvalóvá válik, hogy ha hét hídon lehet átmenni, és mindegyiken pontosan egyszer, akkor ezt az útvonalat nyolc betű jelzi.”
• „... Kidolgoztam egy szabályt, amely alapján könnyen el lehet dönteni - mind erre a problémára, mind minden hasonló problémára -, hogy a betűk ilyen elrendezése megvalósítható-e.

„ 8. Egy ilyen szabály levezetéséhez figyelembe veszek néhány konkrét területet , ahová tetszőleges számú híd vezethet , stb. Ezek közül a hidak közül először egy adott területre vezető hidat veszek figyelembe . Ha egy utazó átmegy ezen a hídon, akkor vagy azon a területen volt, mielőtt átkelt ezen a hídon, vagy ezután is ott lesz . Ezért a hídon átvezető átjárónak a fent leírtak szerinti kijelöléséhez szükséges, hogy a betű egyszer megjelenjen .

• „Ha például három híd vezet a területre, és az utazó mindhárom hídon áthalad, akkor a betű kétszer jelenik meg a hidakon való mozgásának leírásában, függetlenül attól, hogy az útvonala innen indult-e vagy sem. Ugyanígy, ha öt híd vezet a területre, akkor a betű háromszor jelenjen meg a mozgás leírásánál. És ha a hidak száma tetszőleges páratlan szám, akkor ha eggyel növeljük, a kapott szám fele megmutatja, hogy a betűnek hányszor kell előfordulnia .
• “ 9. Ezért a königsbergi hidak esetében, mivel öt híd vezet a szigetre , szükséges, hogy a betű háromszor forduljon elő a hidak mentén történő mozgás leírásában. Ezenkívül a betűknek kétszer kell találkozniuk , mivel három híd vezet a területre, és a betűknek kétszer kell találkozniuk. Ezért a kérdéses útvonalat leíró nyolc betűből álló sorozatban, amely hét hídon halad át, a betűnek háromszor kell előfordulnia, és mindegyik betűnek kétszer kell előfordulnia. Ez azonban nem lehet nyolc betűből álló sorozat. Nyilvánvaló tehát, hogy egy ilyen séta Königsberg hét hídján lehetetlen.”

A probléma megoldásának általánosítása

A feladat általános megoldása során Leonhard Euler bebizonyította, hogy bármely gráf esetén a páratlan élszámú csúcsok száma páros [24] :

• „Először is megjegyzem, hogy a régióba vezető összes hidak száma, „összeadva az összes híd számának kétszeresét adja. Ennek az az oka, hogy minden hidat kétszer számolnak ebben a számlálásban, így az adott területre vezető összes hidat meg kell számolni, minden híd az általa összekapcsolt két területre vezet.

17. Ebből a megfigyelésből az következik, hogy az egyes régiókba vezető összes híd [számainak] összege páros szám, mivel ennek az összegnek a fele pontosan a hidak száma. Ezért nem fordulhat elő, hogy a tetszőleges területre vezető hidak számában pontosan egy páratlan legyen; az sem fordulhat elő, hogy három, öt stb. páratlan szám legyen. Ezért ha a régióba vezető hidak száma "páratlan, akkor az összegük páros".

A cikk végén Leonhard Euler leírta az általános következtetéseket bármely gráfra egészen modern nyelven [24] :

20. Ezért a következő szabály minden lehetséges esetben lehetővé teszi, hogy közvetlenül és minden nehézség nélkül megtudjuk, lehetséges-e ismétlés nélkül végigmenni az összes hídon:

Ha kettőnél több terület van, ahová páratlan számú híd vezet, akkor biztosan kijelenthetjük, hogy egy ilyen séta lehetetlen.

Ha azonban csak két régió van, ahová páratlan számú híd vezet, akkor a séta kivitelezhető, feltéve, hogy e két régió valamelyikéből indul.

Ha végül nincs olyan terület, ahová páratlan számú híd vezet, akkor a megfelelő feltételekkel egy séta kivitelezhető, és bármely területen indulhat.

Ezért ennek a szabálynak a segítségével a felvetett probléma teljesen megoldható.

– Leonhard Euler. Egy pozíciógeometriával kapcsolatos probléma megoldása

Lásd még

• A lovagmozgás problémája
• gráfelmélet
• Euler-ciklus
• Topológia
• Kalinyingrád hídjai
• Az utazó eladó probléma

Jegyzetek

1. ↑ 1 2 Harari Frank. Gráfelmélet, 2003 , p. 13.
2. ↑ 1 2 3 4 Fleischner G. Euler-gráfok és kapcsolódó kérdések, 2002 , p. tizenegy.
3. ↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei, 2008 , p. egy.
4. ↑ Fleischner G. Euler-gráfok és kapcsolódó kérdések, 2002 , p. 17.
5. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertintis, 1736 , p. 129.
6. ↑ Frank Harary Graph Theory, 2007 , p. egy.
7. ↑ Königsberg hídprobléma // Britannica .
8. ↑ Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei, 2008 , p. vii.
9. ↑ Konig Dénes. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24.
10. ↑ Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei, 2008 , p. ix.
11. ↑ Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei, 2008 , p. 151.
12. ↑ 1 2 3 4 5 6 7 8 9 10 11 Gribkovskaia I., Halskau Ø., Laporte G. Königsberg hídjai, 2007 .
13. ↑ Ore O. Graphs and their application, 1965 , p. 6.
14. ↑ 1 2 3 4 Fleischner G. Euler-gráfok és kapcsolódó kérdések, 2002 , p. 26.
15. ↑ A Birodalmi Tudományos Akadémia konferenciájának 1725-1803 közötti üléseinek jegyzőkönyvei . I. kötet 1725-1743, 1897 , p. 220-221.
16. ↑ 1 2 3 Fleischner G. Euler-gráfok és kapcsolódó kérdések, 2002 , p. tizenöt.
17. ↑ Levelek tudósokhoz, 1963 , p. 152-158.
18. ↑ Levelek tudósokhoz, 1963 , p. 330-353.
19. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertiminentis, 1736 .
20. ↑ Ore O. Graphs and their application, 1965 , p. 33.
21. ↑ Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei, 2008 , p. négy.
22. ↑ 1 2 3 4 Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei, 2008 , p. 8-12.
23. ↑ 1 2 Fleischner G. Euler-gráfok és kapcsolódó kérdések, 2002 , p. 27-28.
24. ↑ 1 2 Fleischner G. Euler-gráfok és kapcsolódó kérdések, 2002 , p. 31-32.

Irodalom

• Ore O. Grafikonok és alkalmazásuk / Per. angolról. L. I. Golovina. Szerk. I. M. Yagloma. M.: Mir, 1965. 174 p.: ill.
• A Birodalmi Tudományos Akadémia Konferenciájának 1725-1803 közötti üléseinek jegyzőkönyvei . I. kötet 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Szentpétervár: IAN Nyomda, 1897. 883 p.
• Harary Frank. Gráfelmélet / Per. angolról. V. P. Kozyreva. Szerk. G. P. Gavrilova. 2. kiadás. M.: Szerkesztőség URSS, 2003. 296 p.: ill. ISBN 5-354-00301-6 .
• Fleishner G. Euler grafikonok és kapcsolódó kérdések. M.: Mir, 2002. 335 p.: ill. ISBN 5-03-003115-4 (orosz). ISBN 0-444-88395-9 . [Fleischner H. Euleri grafikonok és kapcsolódó témák. P. 1, V. 1. Amsterdam: North-Holland, 1990.]
• Frich R., Peregud E. E., Matsievsky S. V. A gráfelmélet válogatott fejezetei: Tankönyv / Per. vele. E. E. Pereguda; Paul szerk. S. V. Matszievszkij. Kalinyingrád: Az Orosz Állami Egyetem Kiadója. I. Kant, 2008. 192 p.: ill. ISBN 978-5-88874-880-0 .
• Leonard Euler. Levelek tudósokhoz / Szerk. V. I. Szmirnov akadémikus . - Moszkva-Leningrád: A Szovjetunió Tudományos Akadémiájának Kiadója , 1963. Tartalmazza Yu. Kh. Kopelevich (levél Marinoninak) és T. A. Lukina (Elernek írt levél) eredeti latin leveleinek szövegét és orosz nyelvű fordítását
• Königsberg-híd probléma // 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 gráfelmélet. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283. o.
• Konig Dénes. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkomplexe. Lipcse: Akademische Verlagsgesellschaft MBH, 1936.

Szótárak és enciklopédiák	Nagy dán Britannica (online)