Семь мостов Кёнигсберга: задача, с которой начались графы
В XVIII веке в прусском городе Кёнигсберге, нынешнем Калининграде, была популярная загадка: можно ли прогуляться по городу и пройти по каждому из семи мостов ровно один раз? Ни у кого не получалось. В 1736 году за задачу взялся Леонард Эйлер, и его решение стало началом теории графов.
Для учеников 5–11 классов. Пригодится к заданиям на графы в ОГЭ и ЕГЭ по информатике.
Задача
Город стоял на реке Преголя: два берега и два острова, соединённые семью мостами. Остров Кнайпхоф был связан с берегами четырьмя мостами, второй остров с берегами двумя, и ещё один мост соединял острова. Вопрос: можно ли обойти все мосты, пройдя по каждому ровно один раз?
Идея Эйлера
Эйлер заметил, что форма берегов и длина мостов неважны. Важно только, какие участки суши какими мостами связаны. Он заменил каждый участок точкой, а каждый мост линией. Получилась схема из четырёх точек и семи линий. Сегодня такую схему называют графом, точки вершинами, линии рёбрами.
Дальше рассуждение. Если мы проходим через вершину, то входим по одному ребру и выходим по другому. Значит, у каждой промежуточной вершины рёбер должно быть чётное число. Нечётное число рёбер может быть только у начала и конца пути.
Обойти граф по всем рёбрам по одному разу можно, только если вершин с нечётным числом рёбер 0 или 2.
В Кёнигсберге из одной вершины выходило 5 мостов, а из трёх других по 3. Все четыре нечётные. Значит, прогулка невозможна.
Нарисовать одним росчерком
То же правило отвечает на детскую загадку: можно ли нарисовать фигуру, не отрывая карандаша и не проводя по линии дважды.
Задача
Можно ли одним росчерком нарисовать «домик»: квадрат с двумя диагоналями и крышей-треугольником сверху?
Считаем рёбра у каждой вершины.
Вершина крыши: 2 ребра, чётно.
Верхние углы квадрата: по 4 ребра (две стороны квадрата, диагональ и скат крыши), чётно.
Нижние углы квадрата: по 3 ребра (две стороны и диагональ), нечётно.
Нечётных вершин две, значит, можно. Начинать нужно в одном нижнем углу, заканчивать в другом.
Ответ: Можно, если начать в нижнем углу.
Графы сегодня
Теория графов, начавшаяся с прогулки по мостам, сейчас прокладывает маршруты в навигаторах, строит связи в соцсетях и раскладывает провода на платах. В ЕГЭ по информатике 2027 года появилось целое задание на графы: про кратчайший путь и число путей. Разобрали его в отдельной статье.
А Кёнигсберг стал Калининградом. Часть старых мостов не пережила войну, часть перестроили, так что задача на нынешней карте выглядит уже по-другому.
Разберём на занятии
Разберём эту тему и всё, что с ней связано, на живом занятии: преподаватель видит, как ребёнок решает, и поправляет на первом неверном шаге.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.