Morate prijeći svih 7 mostova. Istorija mostova u Kenigsbergu. Zeleni most, GrüneBrücke

Shop Bridge, Krämerbrücke

Zeleni most, GrüneBrücke

Giblet (radni) most, Koettel brücke

Forge Bridge, Schmitderbrüke

Visoki most, Hohebrücke

Honey Bridge, Honigbrücke

Stanovnici Kenigsberga su se od davnina mučili sa zagonetkom: da li je moguće preći sve mostove u Kenigsbergu, hodajući po svakom samo jednom? Ovaj problem je riješen kako teoretski, na papiru, tako i u praksi, šetnjama - prolazeći upravo tim mostovima. Niko nije uspeo da dokaže da je to nemoguće, ali niko nije mogao da napravi tako „misteriozan“ šetnju preko mostova.

Godine 1736. poznati matematičar, član Petrogradske akademije nauka, Leonhard Euler, preuzeo je na sebe da riješi problem sedam mostova. Iste godine o tome je pisao inženjeru i matematičaru Marioniju. Ojler je napisao da je pronašao pravilo po kojem nije teško izračunati da li je moguće preći sve mostove, a da nijedan od njih ne pređete dva puta. To je nemoguće učiniti na sedam mostova Königsberga.

Upravo zahvaljujući ovom problemu s mostovima na karti starog Königsberga pojavio se još jedan most, uz pomoć kojeg je ostrvo Lomse povezano s južnom stranom. Desilo se ovako. Car (Kaiser) Wilhelm je bio poznat po svojoj jednostavnosti razmišljanja, brzoj reakciji i vojničkoj “uskogrudosti”. Na jednom od prijema na kojima je bio prisutan Kajzer, pozvani naučni umovi odlučili su da se šale s njim: Vilhelmu je pokazana karta Konigsberga, nudeći da se reši problem mostova. Zadatak je očigledno bio nerešiv. Vilhelm je, na opšte iznenađenje, zahtevao olovku i papir, izjavljujući da je problem rešiv i da će ga rešiti za nekoliko minuta. Pronađeni su papir i mastilo, iako niko nije mogao vjerovati da Kaiser Wilhelm ima rješenje za ovaj problem. Na dostavljenom komadu papira, Kajzer je napisao: "Naređujem izgradnju osmog mosta na ostrvu Lomse." Novi most je nazvan Carski most ili Kaiser-brucke.

Ovaj osmi most učinio je problem mosta lakim zabavnim čak i za dijete...

Poštovani kadrovi...

Postoji poznati matematičar, član akademija, vjerovatno profesor ili čak akademik Euler, a tu je jednostavno Kajzer Vilhelm. Ojler je odlučio da se problem ne može riješiti, ali je Wilhelm na pristupačan način pokazao da to nije tako. Ponekad me svađe s vama podsjećaju na gornji primjer iz udžbenika.

Pa, ne želim da ovaj građanin više radi za mene.

Zato što se pokazala kao loša radnica.

Ali ne možemo je otpustiti...

A zašto je to tako?

Dakle... članak je ovakav, odeljak, pasus, pasus...

Treba mi radnik, a ne artikli!

Pročitajte zakon o radu...

Čitam. Zovem ih i otpustim ih sam. I razumijem da će većina vas ostati na nivou "ovog članka, odjeljka, tačke, paragrafa..."

Municipal Autonomous obrazovne ustanove

"Prosječno sveobuhvatne škole br. 6" Perm

Istorija matematike

Stari, stari problem o mostovima u Kenigsbergu

Završio: Železnov Egor,

učenik 10. razreda

Rukovodilac: Orlova E. V.,

nastavnik matematike

2014, Perm

Uvod………………………………………………………………………………………………..3

Historija Königsberških mostova …………………………………………………………………………4

Problem sedam mostova u Kenigsbergu ……………………………………………………..8

Crtanje figura jednim potezom……………………………………….12

Zaključak………………………………………………………………………………………………15

Reference……………………………………………………………………………………….16

Dodatak 1………………………………………………………………………………………………18

Dodatak 2…………………………………………………………………………………………………………22

Dodatak 3……………………………………………………………………………………………23

Dodatak 4 ……………………………………………………………………………………………26

Održavanje

Koenigsberg je istorijsko ime Kalinjingrada, centra najzapadnije regije Rusije, poznatog po blagoj klimi, plažama i proizvodima od ćilibara. Kalinjingrad ima bogatu kulturnu baštinu. Ovdje su nekada živjeli i radili veliki filozof I. Kant, pripovjedač Ernst Theodor Amadeus Hoffmann, fizičar Franz Neumann i mnogi drugi, čija su imena upisana u historiju nauke i stvaralaštva. Jedan interesantan problem povezan je sa Konigsbergom, takozvani problem Konigsberg mosta.

Svrha našeg istraživanja: proučiti istoriju problema Königbergovih mostova, razmotriti njegovo rješenje, saznati ulogu problema u razvoju matematike.

Za postizanje cilja potrebno je riješiti sljedeće zadaci:

proučavanje literature na ovu temu;

sistematizirati gradivo;

odabrati probleme u čijem rješavanju se koristi metoda rješavanja problema Köntgsberg mostova;

sastaviti bibliografsku listu referenci.

Istorija mostova u Königsbergu

Nastalo u grad Kenigsberg (sada) sastojala se od tri formalno nezavisna gradska naselja i još nekoliko „naselja“ i „sela“. Nalazili su se na ostrvima i obalama rijeka(sada Pregolya), dijeleći grad na četiri glavna dijela:, , I . Za komunikaciju između gradskih dijelova koji su već u počeo da se gradi . Zbog stalne vojne opasnosti od susjeda I , kao i zbog građanskih sukoba između gradova Königsberga (in- čak je došlo do rata između gradova, uzrokovanog činjenicom da je Kneiphof prešao na stranu Poljske, a Altstadt i Löbenicht su ostali lojalni) V Königsberg mostovi su imali odbrambene kvalitete. Ispred svakog od mostova izgrađena je odbrambena kula sa podiznim ili dvokrilnim kapijama od hrastovine i oblogom od kovanog željeza. I sami mostovi su dobili karakter odbrambenih objekata. Stubovi nekih mostova imali su petougaoni oblik, tipičan za bastione. Unutar ovih nosača nalazili su se kazamati. Sa oslonaca se moglo pucati kroz brane.

Mostovi su bili mjesto procesija, vjerskih i svečanih procesija, a tokom godina tzv. „prvog ruskog vremena“ (-), kada je Sedmogodišnji rat Königsberg je nakratko postao dio grada, a vjerske procesije su se odvijale preko mostova. Nekada je takva vjerska procesija bila posvećena čak i pravoslavnom prazniku Blagoslova voda rijeke Pregel, što je izazvalo istinsko zanimanje stanovnika Kenigsberga.

Do kraja 19. stoljeća izgrađeno je 7 glavnih mostova u Königsbergu (Dodatak 1).

Najstariji od sedam mostova Prodavnicamost(Krämerbrücke/Krämer-brücke). Izgrađena je 1286. Ime mosta govori za sebe. Trg uz njega bio je mjesto živahne trgovine. Povezivao je dva srednjovjekovna grada Altstadt i Kneiphof. Sagrađena je odmah u kamenu. Godine 1900. obnovljena je i podesiva. Tramvaji su počeli da jure preko mosta. Tokom rata je bio teško oštećen, ali je restauriran sve dok nije demontiran 1972. godine.

Drugi najstariji je bioGreen Bridge (Grüne Brücke/Grune-brücke). Ugrađena je. Ovaj most je povezivao ostrvo Kneiphof sa južnom obalom Pregela. Takođe je bila kamena i imala je tri raspona. Godine 1907. most je obnovljen, srednji raspon je postao pomičan i po njemu su počeli da voze tramvaji. Tokom rata ovaj most je teško oštećen, restauriran, a 1972. godine je demontiran.Naziv mosta potiče od boje koja se tradicionalno koristila za farbanje nosača i raspona mosta. INna Zelenom mostu, glasnik je dijelio pisma koja su stigla u Kenigsberg. Poslovni ljudi grada su se okupili ovdje u iščekivanju prepiske. Ovdje su, čekajući poštu, razgovarali o svojim poslovima. Ne čudi što se nalazi u neposrednoj blizini Zelenog mosta uizgrađen je trgovački centar Königsberg. IN na drugoj obali Pregela, ali i u neposrednoj blizini Zelenog mosta, sagrađena je nova zgrada trgovačke berze, koja je opstala do danas (danas Palata kulture pomoraca).Godine 1972. izgrađen je Estakadnyj most umjesto Zelenog i Lavočnog mosta.

Nakon što su izgrađeni Lavočni i ZeleniRadni most (Koettelbrucke/Kettel ili Kittel-brücke), također povezuje Kneiphof i Forstadt. Ponekad se ime prevodi i kao Giblet Bridge. Obje opcije prijevoda nisu idealne, jer nemački naziv potičea na ruskom znači otprilike „radnik, pomoćnik, namijenjen za prevoz smeća“ itd. Ovaj most je bio ugrađeno . Povezivao je grad Kneiphof sa predgrađem Forstadt. Most je bio napola kamen, a rasponi drveni. Godine 1621., tokom velike poplave, most je otkinut i odnesen u rijeku. Most je vraćen na svoje mjesto. Godine 1886. zamijenjen je novim, čeličnim, trorasponskim, pokretnim. Po njoj su vozili i tramvaji. Most je uništen tokomi kasnije nije obnovljena.

Sedam mostova Kenigsberga - Wikipedia (ru /wikipedia .ord)

Teorija grafova – web stranica www .ref .by /refs

Aneks 1

Lavochny Bridge

Green Bridge

Giblet Bridge

Kuznečni most

Drveni most

Visoki most

Honey Bridge. Pogled sa strane na

bivši pokretni most.

Honey Bridge. Ostaci podesivog mehanizma.

Kaiser Bridge

Dodatak 2

Leonard Euler

N Nemački i ruski matematičar, mehaničar i fizičar. Rođen 15. aprila 1707. u Bazelu. Studirao je na Univerzitetu u Bazelu (1720–1724), gdje mu je učitelj bio Johann Bernoulli. Godine 1722. stekao je zvanje magistra umjetnosti. Godine 1727. preselio se u Sankt Peterburg, gdje je dobio mjesto vanrednog profesora na novoosnovanoj Akademiji nauka i umjetnosti. Godine 1730. postao je profesor fizike, 1733. godine - profesor matematike. Tokom 14 godina svog prvog boravka u Sankt Peterburgu, Ojler je objavio više od 50 radova. Godine 1741–1766 radio je na Berlinskoj akademiji nauka pod posebnim pokroviteljstvom Fridriha II i napisao mnoge eseje, pokrivajući u suštini sve dijelove čiste i primijenjene matematike. Godine 1766, na poziv Katarine II, Ojler se vratio u Rusiju. Ubrzo po dolasku u Sankt Peterburg potpuno je izgubio vid zbog katarakte, ali je zahvaljujući odličnom pamćenju i sposobnosti da vrši mentalne proračune učio do kraja života. naučno istraživanje: za to vrijeme objavio je oko 400 djela, ali njihov ukupan broj prelazi 850. Ojler je umro u Sankt Peterburgu 18. septembra 1783. godine.

Ojlerovi radovi svjedoče o izuzetnoj svestranosti autora. Njegova rasprava o nebeskoj mehanici “Teorija kretanja planeta i kometa” je nadaleko poznata. Autor knjiga o hidraulici, brodogradnji, artiljeriji. Ojler je bio najpoznatiji po svom istraživanju čiste matematike.

Dodatak 3

Zadaci

Z
problem 1(problem o mostovima u Lenjingradu). U jednoj od sala Kuće zabavne nauke u Sankt Peterburgu, posetiocima je pokazan dijagram gradskih mostova (sl.). Bilo je potrebno obići svih 17 mostova koji povezuju ostrva i obale Neve, na kojima se nalazi Sankt Peterburg. Morate obići tako da se svaki most prijeđe jednom.

I odsijecanje blokova,

Iznenada izaći iz mraka

Sankt Peterburg kanali,

Mostovi Sankt Peterburga!

(N. Agnivtsev)

D dokazati da je potrebna jednoznačna obilaznica svih mostova Sankt Peterburga tog vremena moguća, ali se ne može zatvoriti, tj.V tačka od koje je počelo.

Zadatak 2. Na jezeru se nalazi sedam ostrva koja su međusobno povezana kao što je prikazano na slici. Na koje ostrvo treba putnike odvesti brodom da mogu prijeći svaki most i to samo jednom? Zašto se putnici ne mogu prevesti do ostrva A? 17

Z sreća 3. (U potrazi za blagom) .

Na sl. prikazuje plan tamnice, u čijoj je jednoj od prostorija skriveno viteško bogatstvo. Da biste sigurno ušli u ovu prostoriju, morate ući kroz određenu kapiju u jednu od vanjskih prostorija tamnice, proći kroz svih 29 vrata u nizu, isključivši alarm. Ne možete dvaput proći kroz ista vrata. Odredite broj sobe u kojoj je skriveno blago i kapije kroz koju treba ući? 20

problem 4. Pavlik, strastveni biciklista, prikazan na tabla dio plana područja i naselja (Sl. 8), gdje je živio prošlog ljeta. Prema Pavlikovoj priči, nedaleko od sela koje se nalazi uz obalu reke Oje nalazi se malo duboko jezero koje se hrani podzemnim izvorima. Od nje potiče Oja, koja je na ulazu u selo podeljena na dve odvojene reke, povezane prirodnim kanalom tako da zeleni oštarwok(na slici označenoj slovomA) sa plažom i sportskim terenom. DalekOIza sela se obje rječice spajaju u široku rijeku. Tvrdi to Pavlik, vraćajući se biciklom sa sportalokacija koja se nalazi na ostrvu, dom (na slici slovD ), jednom pređe preko svih osam mostova prikazanih na planu, ne prekidajući kretanje. Naši stručnjaci za teoriju ovakvih zagonetki označili su slovimaA, B, C, D delovi sela, odvojeni rekom (deonice su čvorovi mreže, mostovi su ogranci), i utvrđeno je da je jednosmerni pravac koji počinje uA (neparni čvor), je moguće, ali svakako mora završiti na B - u drugom neparnom čvoru, druga dva čvoraWITH ID - čak. Ali Pavlik govori istinu: njegov put odA VD zaista je trčao duž svih osam mostova i bio je jednoličan. Šta je ovde? Šta ti misliš?

Z problem 5 . Engleski matematičar L. Carroll (autor međunarodnog poznate knjige“Alisa u zemlji čuda”, “Alisa kroz ogledalo” itd.) volio je da zadaje svojim malim prijateljima slagalicu da šetaju oko figure (slika 9)jednim potezom olovke i bez prolaska dvaput kroz bilo koji dio konture. Prelazak linija je bio dozvoljen. Ovaj problem se može jednostavno riješiti.

Zakomplikujmo to dodatnim zahtjevom: sa svakim prijelazom kroz čvor (smatrajući točke presjeka linija na slici kao čvorove), smjer prelaska se mora promijeniti za 90°. (Počevši od bilo kojeg čvora, morat ćete napraviti 23 okreta) 6 .

Problem 6 . (Muha u tegli) Muva se popela u teglu šećera. Tegla ima oblik kocke. Može li muva uzastopno obići svih 12 ivica kocke, a da ne pređe dva puta preko iste ivice? Skakanje i letenje s mjesta na mjesto nije dozvoljeno. 22

Z problem 7 . Slika prikazuje pticu. Da li je moguće nacrtati jednim potezom?

Z problem 8 . OnSlika 10 prikazuje skicu jednog od Eulerovih portreta. Umjetnik ga je reproducirao jednim potezom olovke (samo je kosa nacrtana posebno). Gdje se na slici nalaze početak i kraj unikurzalne konture? Ponovite pokret olovke umjetnika (kosa i isprekidane linije na crtežu nisu uključeneVobilazni put) 6 .

Fig.10

sreća 9. Nacrtajte sljedeće oblike jednim potezom. (Takve figure se nazivaju unikursalnim (od latinskog unus - jedan, cursus - put)).

Dodatak 4

Rješavanje problema

1

.

3 . Da biste to riješili, morate napraviti graf, gdje su vrhovi brojevi soba, a ivice vrata.

Neparni vrhovi: 6, 18. Pošto je broj neparnih vrhova = 2, moguće je bezbjedno ući u prostoriju sa blagom.

Morate započeti putovanje kroz kapiju IN, i završiti u prostoriji br. 18 .

5. Primjer potrebnog obilaznice dat je na slici

6 . Rubovi i vrhovi kocke formiraju graf, čijih svih 8 vrhova ima višestrukost 3 i stoga je prelazak koji je potreban uslovom nemoguć.

7. Uzimajući tačke preseka prave kao vrhove grafa, dobijamo 7 vrhova, od kojih samo dva imaju neparan stepen. Dakle, u ovom grafu postoji Eulerova putanja, što znači da se ona (tj. ptica) može nacrtati jednim potezom. Morate započeti stazu na jednom neparnom vrhu i završiti na drugom.

8. Potrebno je započeti obilazak od neparnog čvora u kutu desnog oka i završiti na neparnom čvoru obrve iznad lijevog oka (isprekidane linije nisu uključene u mrežu). Svi ostali čvorovi na slici su parni.

9 .

Razmotrivši ovaj problem, Euler je 1736. godine dokazao da je to nemoguće, i razmatrao je više zajednički zadatak: koja područja, odvojena riječnim rukavcima i povezana mostovima, mogu se obići obilaskom svakog mosta tačno jednom, a koja su nemoguća.

Königsberg mostovi">

Hajde da malo izmenimo problem. Svako područje koje se razmatra, odvojeno rijekom, označit ćemo točkom, a mostove koji ih povezuju linijskim segmentom (ne nužno pravom linijom). Tada ćemo, umjesto plana, jednostavno raditi s određenom figurom sastavljenom od segmenata krivih i pravih linija. U modernoj matematici takve figure se nazivaju grafovi, segmenti se nazivaju ivicama, a tačke koje spajaju ivice nazivaju se vrhovi. Tada je izvorni problem ekvivalentan sljedećem: da li je moguće nacrtati dati graf bez podizanja olovke sa papira, odnosno na način da se svaki njegov rub prijeđe tačno jednom?

Takvi grafovi, koji se mogu nacrtati bez podizanja olovke sa papira, nazivaju se unikursalnim (od latinskog unus cursus - jedan put), ili Eulerovim. Dakle, problem se postavlja ovako: pod kojim uslovima je graf unikurzalan? Jasno je da unikurzalan graf neće prestati biti unikurzalan ako se promijeni dužina ili oblik njegovih rubova, kao i lokacija vrhova - sve dok se ne promijeni veza vrhova po rubovima (u u smislu da ako su dva vrha povezana, oni trebaju ostati povezani, a ako su razdvojeni – onda nepovezani).

Ako je graf unikurzalan, tada će i topološki ekvivalentan graf biti unikurzalan. Unikurznost je stoga topološko svojstvo grafa.

Prvo, moramo razlikovati povezane grafove od nepovezanih. Povezane figure su one takve da bilo koje dvije tačke mogu biti povezane nekom putanjom koja pripada ovoj figuri. Na primjer, većina slova ruske abecede je povezana, ali slovo Y nije: nemoguće je pomicati se s njegove lijeve polovine na desno duž tačaka koje pripadaju ovom slovu. Povezanost je topološko svojstvo: ne mijenja se kada se figura transformira bez prekida ili lijepljenja. Jasno je da ako je graf unikurzalan, onda mora biti povezan.

Drugo, razmotrite vrhove grafa. Indeksom vrha ćemo nazvati broj ivica koje se nalaze u ovom vrhu. Sada se zapitajmo: čemu mogu biti jednaki indeksi vrhova unikurzalnog grafa?

Ovdje mogu postojati dva slučaja: linija koja crta graf može početi i završiti u istoj tački (nazovimo je "zatvorenom putanjom"), ili možda u različitim tačkama (nazovimo je "otvorena staza"). Pokušajte sami nacrtati takve linije - sa bilo kojim samopresjecima koji želite - dvostruko, trostruko, itd. (radi jasnoće, bolje je da nema više od 15 rubova).

Lako je vidjeti da u zatvorenoj putanji svi vrhovi imaju paran indeks, a na otvorenoj stazi tačno dva imaju neparan indeks (ovo je početak i kraj puta). Činjenica je da ako vrh nije početni ili konačni, onda, nakon što dođete do njega, morate izaći iz njega - dakle, koliko ivica uđe u njega, isti broj izlazi iz njega, a ukupan broj dolaznih i odlaznih ivice će biti ujednačene. Ako se početni vrh poklapa sa konačnim vrhom, tada je i njegov indeks paran: broj ivica koje su izašle iz njega, isti broj koji je ušao. A ako se početna točka ne poklapa sa završnom točkom, onda su njihovi indeksi neparni: potrebno je jednom izaći iz početne točke, a zatim, ako se vratimo na nju, onda opet izaći, ako se vratimo ponovo, izaći ponovo itd. .; ali treba da dođemo do završnog, pa ako ga onda napustimo, onda se opet trebamo vratiti itd.

Dakle, da bi graf bio unikurzalan, potrebno je da svi njegovi vrhovi imaju paran indeks ili da broj vrhova sa neparnim indeksom bude jednak dva.

Izračunajte indekse njegovih vrhova i uvjerite se da on nikako ne može biti unikurzalan. Zato niste uspeli kada ste hteli da obiđete sve mostove...

Postavlja se pitanje: ako povezani graf nema vrhove sa neparnim indeksom ili tačno dva takva vrha, da li je graf nužno unikurzalan? Može se striktno dokazati da da! Dakle, jednoznačnost je jedinstveno povezana sa brojem vrhova sa neparnim indeksom.

Vježba: izgradite još jedan most na dijagramu Königsberg mostova - gdje želite - tako da se nastalim mostovima može prošetati, nakon što ste svaki posjetili tačno jednom; zaista idi ovim putem.

Sada postoji još jedan zanimljiva činjenica: Ispostavilo se da se svaki sistem područja povezanih mostovima može zaobići ako svaki most trebate posjetiti tačno dva puta! Pokušajte to sami dokazati.

FORUM NOVOSTI
Teorija vitezova etera

01.10.2019 - 05:20: -> - Karim_Khaidarov.
30.09.2019 - 12:51:

Osnove teorije grafova kao matematičke nauke koji je 1736. postavio Leonhard Euler, razmatrajući problem Kenigsberških mostova. Danas je ovaj zadatak postao klasičan.

Nekadašnji Koenigsberg (danas Kalinjingrad) nalazi se na rijeci Pregel. Unutar grada rijeka pere dva ostrva. Gradili su se mostovi od obala do ostrva. Stari mostovi nisu sačuvani, ali je ostala karta grada na kojoj su prikazani. Koenigsbergeri su posetiocima nudili sledeći zadatak: da pređu sve mostove i vrate se na početnu tačku, a svaki most je trebalo posetiti samo jednom.

Problem sedam mostova u Kenigsbergu

Problem sedam Kenigsberških mostova ili Problem Königsberških mostova (njem. Königsberger Brückenproblem) - drevni matematički problem, koji je pitao kako se može hodati preko svih sedam Kenigsbergovih mostova, a da nijedan od njih ne pređe dva puta. Prvi ga je 1736. godine riješio njemački i ruski matematičar Leonhard Euler.

Sljedeća zagonetka odavno je uobičajena među stanovnicima Königsberga: kako preći sve mostove (preko rijeke Pregolya) a da ni jedan od njih ne pređete dva puta. Mnogi Königsbergeri pokušali su riješiti ovaj problem i teoretski i praktično tokom šetnji. Međutim, niko nije mogao dokazati ili opovrgnuti mogućnost postojanja takve rute.

Godine 1736. zainteresovao se problem sedam mostova izvanredan matematičar, član Peterburške akademije nauka Leonhard Euler, o čemu je pisao u pismu italijanskom matematičaru i inženjeru Marioniju od 13. marta 1736. godine. U ovom pismu Ojler piše da je uspeo da pronađe pravilo pomoću kojeg je lako utvrditi da li je moguće preći preko svih mostova, a da ni jedan od njih ne pređete dva puta. Odgovor je bio “ne”.

Rješavanje problema prema Leonhardu Ojleru

U pojednostavljenom dijagramu dijelova grada (grafa), mostovi odgovaraju linijama (lukovi grafa), a dijelovi grada odgovaraju tačkama koje spajaju linije (vrhovi grafa). Tokom svog rasuđivanja, Euler je došao do sljedećih zaključaka:

Broj neparnih vrhova (vrhova do kojih vodi neparan broj ivica) grafa mora biti paran. Ne može postojati graf koji ima neparan broj neparnih vrhova.
Ako su svi vrhovi grafa parni, onda možete nacrtati graf bez podizanja olovke sa papira i možete početi od bilo kojeg vrha grafa i završiti ga na istom vrhu.
Graf sa više od dva neparna vrha ne može se nacrtati jednim potezom.
Graf Königsberg mostova je imao četiri (plava) neparna vrha (odnosno, sve), stoga je nemoguće preći preko svih mostova, a da jedan od njih ne pređete dva puta

Teorija grafova koju je kreirao Euler našla je veoma široku primenu u transportnim i komunikacionim sistemima (na primer, za proučavanje samih sistema, kreiranje optimalnih ruta za isporuku robe ili rutiranje podataka na Internetu).

Dalja istorija mostova u Kenigsbergu

Godine 1905. izgrađen je Carski most, koji je kasnije uništen bombardovanjem tokom Drugog svetskog rata. Postoji legenda da je ovaj most sagrađen po nalogu samog Kajzera, koji nije uspeo da reši problem Königsberških mostova i postao je žrtva šale koju su na njegov račun izveli učeni umovi prisutni na društvenom prijemu (ako ste dodajte osmi most, tada problem postaje rješiv). Jubilarni most izgrađen je na stubovima Carskog mosta 2005. godine. On ovog trenutka u Kalinjingradu postoji sedam mostova, a graf izgrađen na osnovu ostrva i mostova Kalinjingrada još uvek nema Ojlerovu stazu.

Jeste li znali da je sedam mostova grada Koeningsberga (sada se ovaj grad zove Kalinjingrad) postalo „krivci“ za stvaranje teorije grafova Leonharda Eulera (graf je određeni broj čvorova (vrhova) povezanih rubovima) . Ali kako se to dogodilo?

Dva ostrva i obale na reci Pregel, na kojoj se nalazio Koeningsberg, bila su povezana sa 7 mostova. Poznati filozof a naučnik Imanuel Kant, šetajući mostovima grada Kenigsberga, postavio je problem poznat svima u svetu kao problem 7 Kenigsberških mostova: da li je moguće preći preko svih ovih mostova i istovremeno se vratiti na početnu tačku rute tako da se svaki most pređe samo jednom . Mnogi su pokušali riješiti ovaj problem i praktično i teoretski. Ali nikome nije pošlo za rukom, niti je bilo moguće dokazati da je to nemoguće čak ni teoretski. Stoga se, prema istorijskim podacima, veruje da su u 17. veku stanovnici formirali posebnu tradiciju: dok šetate gradom, samo jednom pređite sve mostove. Ali, kao što znate, niko nije uspeo.

Godine 1736. ovaj problem je zainteresovao naučnika Leonharda Ojlera, izvanrednog i poznatog matematičara i člana Petrogradske akademije nauka. O tome je pisao u pismu svom prijatelju, naučniku, italijanskom inženjeru i matematičaru Marioniju, od 13. marta 1736. godine. Pronašao je pravilo pomoću kojeg je lako i jednostavno mogao dobiti odgovor na ovo pitanje koje je zanimalo svakoga. U slučaju grada Koeningsberga i njegovih mostova to se pokazalo nemogućim.

U procesu svog rasuđivanja, Euler je došao do sljedećih teorijskih zaključaka:

Broj neparnih vrhova (vrhova do kojih vodi neparan broj ivica) grafa mora biti paran. Ne može postojati graf koji ima neparan broj neparnih vrhova.

Ako su svi vrhovi grafa parni, onda možete nacrtati graf bez podizanja olovke sa papira i možete početi od bilo kojeg vrha grafa i završiti ga na istom vrhu.

Graf sa više od 2 neparna vrha ne može se nacrtati jednim potezom

Ako uzmemo u obzir ovo pravilo za 7 mostova Koeningsberga, tada su dijelovi grada na slici (grafu) označeni vrhovima, a mostovi su označeni rubovima koji povezuju ove vrhove. Graf 7 Königsberg mostova imao je 4 neparna vrha (tj. svi su mu vrhovi bili neparni), stoga je nemoguće proći preko svih 7 mostova, a da kroz bilo koji od njih ne prođete dva puta.

Činilo bi se da tako neobično otkriće ne može imati nikakvog prava primena i praktične koristi. Ali nađena je upotreba, i još ponešto. Teorija grafova, koju je kreirao Leonhard Euler, činila je osnovu za projektovanje komunikacionih i transportnih sistema, koristi se u programiranju i računarstvu, fizici, hemiji i mnogim drugim naukama i oblastima.

Ali najzanimljivije je to što istoričari veruju da postoji osoba koja je rešila ovaj problem; mogao je da pređe sve mostove samo jednom, iako teoretski, ali rešenje je postojalo... I ovako se desilo...

Kaiser (car) Wilhelm je bio poznat po svojoj jednostavnosti razmišljanja, direktnosti i vojničkoj „uskogrudosti“. Jednog dana, dok je bio na nekom društvenom događaju, zamalo je postao žrtva šale koju su učeni umovi prisutni na prijemu odlučili odsvirati na njegov račun. Pokazali su Kajzeru kartu grada Königsberga i zamolili ga da pokuša riješiti ovaj čuveni problem, koji je, po definiciji, jednostavno bio nerješiv. Na opšte iznenađenje, Kajzer je tražio komad papira i olovku, a istovremeno je precizirao da će ovaj problem rešiti za samo minut i po. Zapanjeni naučnici nisu mogli vjerovati svojim ušima, ali su mu brzo pronađeni mastilo i papir. Kajzer je stavio komad papira na sto, uzeo olovku i napisao: „Naređujem izgradnju osmog mosta na ostrvu Lomze. I ceo problem je rešen.....

Tako je u gradu Königsbergu nastao novi 8. most preko rijeke, koji je nazvan Kajzerov most. A sada čak i dijete može riješiti problem sa 8 mostova .