Кёнигсберг - родина теории графов

Возникновение теории графов связано с математическими головоломками. Достаточно продолжительное время теория графов была "несерьезна" и целиком связана с играми и развлечениями. Судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играх.
___

В старом Кёнигсберге (нынешний Калининград) было 7 мостов между частями города.
Вопрос был простой и жизненный:
Можно ли пройти по всем мостам ровно один раз и вернуться назад?
___

Задачу в 1736 году разобрал Леонард Эйлер. Он предположил, что важна только степень вершины (сколько мостов выходит из точки), и сформулировал несколько правил:
• если у всех вершин четная степень, можно пройти и вернуться (эйлеров цикл)
• если ровно 2 вершины нечетные, можно пройти, но не вернуться
• если больше - невозможно.

В той задаче у всех 4 вершин степень была нечетной, следовательно, пройти все мосты ровно один раз невозможно.

В итоге Эйлер не только решил задачу, но и заложил основы теории графов, которая сегодня используется в разных областях науки и техники.
___

Вторая мировая война внесла свои коррективы. Мосты были уничтожены. Частично сохранился (восстановлен) только медовый мост.