Теория:
Великое количество мостов, семь в общей сложности, пересекают мудро плывущую реку Прегель в древнем поселении Кёнигсберге, что в наши дни именуется Калининградом.
Рис. \(1\). Семь мостов через реку
Учёный Леонард Эйлер выяснил, что невозможно пройти по всем мостам города ровно один раз и стать счастливым и богатым, как гласила старая легенда.
Даже при максимальных усилиях жителей, никому не удавалось выполнить эту задачу. Не имеет значения, с какого моста начинал бы свой путь искатель приключений.
Рис. \(2\). Леонард Эйлер — великий математик
Эйлер в своём решении задачи доказал теорему о том, что в графе, где пройден путь через все рёбра по одному разу, количество вершин нечётной степени не превышает двух.
Также верно утверждение в обратную сторону: если в графе не более двух вершин нечётной степени, то в этом графе можно найти путь, проходящий через все рёбра ровно один раз.
Рассмотрим применение этой теории на примере задачи о мостах: сушу представим в виде вершин, а мосты — в виде рёбер графа.
Рис. \(3\). План города в виде графа
Невозможно обойти данный граф эйлеровым путём, поскольку все его четыре вершины имеют нечётную степень: вершины А, В и Г имеют степень \(3\), а вершина Б — степень \(5\).
Источники:
Рис. 1. Мосты. © ЯКласс.
Рис. 2. Эйлер. Лицензия Shutterstock. (Дата обращения: 25.01.2025.)
Рис. 3. Граф. © ЯКласс.