Problém siedmich mostov v Königsbergu

Po prvé, Euler poukázal na to, že na výbere trasy vo vnútri každej pevniny nezáleží. Jedinou dôležitou vlastnosťou trasy je poradie, v akom sa prechádzajú mosty. Zmenil teda problém na abstraktné podmienky. Tým položil základy teórie grafov. Odstránil všetky vlastnosti okrem zoznamu pevnín a mostov, ktoré ich spájajú. V jazyku teórie grafov nahradil každú masu zeme abstraktným "vrcholom" alebo uzlom. Potom nahradil každý most abstraktným spojením, "hranou". Hrana (cesta) zaznamenávala, ktoré dva vrcholy (zemské masy) boli spojené. Týmto spôsobom vytvoril graf.

→ →

Nakreslený graf je abstraktným obrazom problému. Hrany sa teda môžu spájať ľubovoľným spôsobom. Dôležité je len to, či sú dva body spojené alebo nie. Zmenou obrázka grafu sa samotný graf nemení.

Ďalej si Euler všimol, že (s výnimkou koncových bodov prechádzky) vždy, keď sa do vrcholu vstupuje mostom, opúšťa sa vrchol mostom. V každej prechádzke grafom sa počet vstupov do vrcholu rovná počtu výstupov z neho. Ak každý most prešiel presne raz, vyplýva z toho, že pre každú zemskú masu (okrem tých, ktoré boli vybrané pre začiatok a cieľ) musí byť počet mostov, ktoré sa dotýkajú tejto zemskej masy, párny. Je to preto, že ak existuje n mostov, prechádza sa cez ňu presne 2n-krát. Všetkých štyroch pevnín v pôvodnom probléme sa však dotýka nepárny počet mostov (jedného sa dotýka 5 mostov a každého z ostatných troch sa dotýkajú 3 mosty). Existujú najviac dve hmoty, ktoré môžu byť koncovými bodmi prechádzky. Takže tvrdenie o prechádzke, ktorá prechádza cez každý most raz, vedie k rozporu.

V modernom jazyku Euler ukázal, že to, či je možné prejsť grafom, v ktorom každá hrana prechádza raz, závisí od stupňov uzlov. Stupeň uzla je počet hrán, ktoré sa ho dotýkajú. Euler ukazuje, že nevyhnutnou podmienkou prechodu je, aby bol graf spojitý a mal presne nula alebo dva uzly nepárneho stupňa. Tento Eulerov výsledok neskôr dokázal Carl Hierholzer. Takáto prechádzka sa teraz nazýva Eulerova cesta alebo Eulerova prechádzka. Ak existujú uzly nepárneho stupňa, potom každá Eulerova cesta začína v jednom z nich a končí v druhom. Keďže graf reprezentujúci historický Königsberg má štyri uzly nepárneho stupňa, nemôže mať Eulerovu cestu.

Eulerova práca bola 26. augusta 1735 predložená Petrohradskej akadémii. Bola publikovaná ako Solutio problematis ad geometriam situs pertinentis (Riešenie problému týkajúceho sa geometrie polohy) v časopise Commentarii academiae scientiarum Petropolitanae v roku 1741. V angličtine je k dispozícii v publikácii The World of Mathematics.

V dejinách matematiky sa Eulerovo riešenie problému Königsberského mosta považuje za prvú vetu teórie grafov. Teória grafov je v súčasnosti všeobecne považovaná za odvetvie kombinatoriky.

Dva z pôvodných siedmich mostov boli zničené počas bombardovania Königsbergu počas druhej svetovej vojny. Ďalšie dva boli neskôr zbúrané. Nahradila ich moderná diaľnica. Ostatné tri mosty zostali, hoci len dva z nich pochádzajú z Eulerových čias (jeden bol prestavaný v roku 1935). V roku 2000 sa teda v Kaliningrade nachádzalo päť mostov.

Z hľadiska teórie grafov majú teraz dva z uzlov stupeň 2 a ďalšie dva majú stupeň 3. Preto je teraz možná Eulerova cesta, ale keďže musí začínať na jednom ostrove a končiť na druhom, je pre turistov nepraktická.

• Ikosian hra
• Hamiltonova cesta
• Voda, plyn a elektrina
• Problém obchodného cestujúceho