Мосты Кёнигсберга стали источником вдохновения для одной из первых задач теории графов. В Санкт-Петербурге тоже есть место, связанное с семью мостами — Семимостье.
Задача о семи мостах Кёнигсберга
Задача заключалась в следующем: можно ли пройти по всем семи мостам Кёнигсберга, не проходя по одному и тому же мосту дважды? Эйлер доказал, что такое путешествие невозможно, положив тем самым начало теории графов. В общем виде он сформулировал критерии существования эйлерова пути в графах. Он показал, что если в графе больше двух вершин с нечётной степенью (то есть вершин, соединённых нечётным числом рёбер), то эйлеров путь невозможен, так как в таком случае невозможно войти и выйти из всех этих вершин ровно один раз.
Город Кёнигсберг, расположенный на островах с семью мостами, имел более двух таких вершин, что и делало задачу невыполнимой.
Семимостье в Санкт-Петербурге
В Санкт-Петербурге существует точка, называемая Семимостьем. Она расположена на пересечении Крюкова и Грибоедова каналов и реки Мойки. Если встать на Пикалов мост, то можно увидеть сразу семь мостов:
- Пикалов мост
- Красногвардейский мост
- Ново-Никольский мост
- Старо-Никольский мост
- Могилёвский мост
- Смежный мост
- Кашин мост
Связь с теорией графов
Хотя Семимостье не связано с конкретной математической задачей, его структура делает его интересным объектом для графового анализа. Можно рассматривать его как граф, где мосты — это рёбра, а суша — вершины. В отличие от задачи Кёнигсберга, здесь можно спланировать маршрут, проходящий по всем мостам, что делает его отличным примером для изучения эйлеровых циклов и маршрутов в реальных условиях. . Согласно теории графов, маршрут возможен, если в графе существует либо эйлеров цикл (когда все вершины имеют чётную степень), либо эйлеров путь (когда ровно две вершины имеют нечётную степень). В случае Семимостья граф, представляющий мосты и перекрестки каналов, позволяет составить такой маршрут, так как у него есть ровно 2 вершины с нечетной степенью.
