(Задача о Кёнигсберских мостах.) На рисунке изображены семь мостов, которые соединяли части города Кёнигсберг (ныне Калининград). Среди жителей Кёнигсберга была известна задача: как устроить прогулку по городу, чтобы пройти по каждому из семи мостов ровно один раз? Можно ли так построить маршрут? Если можно — постройте, если нет — объясните, почему это невозможно.

Анализ задачи (Кёнигсбергские мосты):

Эта задача является классическим примером применения теории графов. Её можно представить в виде графа, где:

• Вершины — это участки суши (два берега реки и два острова). На рисунке их 4: АЛЬШТАДТ, КУЗНЕЧНЫЙ МОСТ (область вокруг него), ЛЕБЕНИХТ, О. КНАЙПХОФ, О. ЛОМЗЕЕ.
• Рёбра — это мосты, соединяющие эти участки суши. На рисунке 7 мостов.

Представим граф:

• Вершина 1 (АЛЬШТАДТ) соединена с: О. КНАЙПХОФ (мост 1), КУЗНЕЧНЫЙ МОСТ (мост 2).
• Вершина 2 (КУЗНЕЧНЫЙ МОСТ) соединена с: АЛЬШТАДТ (мост 2), О. КНАЙПХОФ (мост 6), ЛЕБЕНИХТ (мост 4).
• Вершина 3 (ЛЕБЕНИХТ) соединена с: КУЗНЕЧНЫЙ МОСТ (мост 4), О. ЛОМЗЕЕ (мост 7).
• Вершина 4 (О. КНАЙПХОФ) соединена с: АЛЬШТАДТ (мост 1), ЛАВОЧНЫЙ МОСТ (мост 5), КУЗНЕЧНЫЙ МОСТ (мост 6), МЕДОВЫЙ МОСТ (мост 3).
• Вершина 5 (О. ЛОМЗЕЕ) соединена с: МЕДОВЫЙ МОСТ (мост 3), ВЫСОКИЙ МОСТ (мост 7).

Степени вершин (количество мостов, подходящих к каждому участку суши):

• АЛЬШТАДТ: 2 моста (1, 2). Степень = 2.
• КУЗНЕЧНЫЙ МОСТ: 3 моста (2, 6, 4). Степень = 3.
• ЛЕБЕНИХТ: 2 моста (4, 7). Степень = 2.
• О. КНАЙПХОФ: 4 моста (1, 5, 6, 3). Степень = 4.
• О. ЛОМЗЕЕ: 2 моста (3, 7). Степень = 2.

Правило для существования такого маршрута (Эйлеров путь):

В графе, где рёбра нужно пройти ровно один раз, существует Эйлеров путь (или Эйлеров цикл, если начинать и заканчивать в одной точке), если:

• Либо все вершины имеют чётную степень (тогда это Эйлеров цикл, можно начать и закончить в любой точке).
• Либо ровно две вершины имеют нечётную степень (тогда это Эйлеров путь, начинать нужно в одной из вершин с нечётной степенью и заканчивать в другой).

Анализ степеней вершин в задаче о Кёнигсберских мостах:

У нас вершины имеют степени: 2, 3, 2, 4, 2. Здесь две вершины (КУЗНЕЧНЫЙ МОСТ и О. КНАЙПХОФ) имеют нечётную степень (3 и 4 соответственно). Нет, подождите, вершина О. КНАЙПХОФ имеет степень 4 (чётная), а КУЗНЕЧНЫЙ МОСТ — степень 3 (нечётная). А что насчет других? Давайте пересчитаем внимательно по картинке:

1. АЛЬШТАДТ: мосты 1, 2. Степень = 2 (чётная).

2. О. КНАЙПХОФ: мосты 1, 3, 5, 6. Степень = 4 (чётная).

3. ЛЕБЕНИХТ: мосты 4, 7. Степень = 2 (чётная).

4. О. ЛОМЗЕЕ: мосты 3, 7. Степень = 2 (чётная).

5. Участок между мостами 2, 6, 4 (Кузнечный): мосты 2, 4, 6. Степень = 3 (нечётная).

6. Участок между мостами 3, 5 (Лавочный/Медовый): мосты 3, 5. Степень = 2 (чётная).

7. Участок между мостами 4, 7 (Деревянный/Высокий): мосты 4, 7. Степень = 2 (чётная).

Ах, вот в чем дело! Я неправильно определил вершины. Давайте определим их по участкам суши:

Участки суши (вершины):

• A: АЛЬШТАДТ
• B: О. КНАЙПХОФ
• C: ЛЕБЕНИХТ
• D: О. ЛОМЗЕЕ

Мосты (рёбра) и их связи:

• Мост 1: A — B
• Мост 2: A — (участок между мостами 2, 6, 4)
• Мост 3: B — D
• Мост 4: (участок между мостами 2, 6, 4) — C
• Мост 5: B — (участок между мостами 3, 5)
• Мост 6: B — (участок между мостами 2, 6, 4)
• Мост 7: (участок между мостами 3, 5) — C

Это всё ещё не совсем точно. Давайте смотреть на карту как на граф, где реки и острова — это зоны, а мосты — пути между ними.

Вершины (участки суши):

• 1 (АЛЬШТАДТ)
• 2 (О. КНАЙПХОФ)
• 3 (ЛЕБЕНИХТ)
• 4 (О. ЛОМЗЕЕ)

Мосты (рёбра) и связи:

• Мост 1: 1 — 2
• Мост 5: 1 — 2
• Мост 2: 1 — 3
• Мост 6: 2 — 3
• Мост 3: 2 — 4
• Мост 7: 3 — 4
• Мост 4: (часть суши, которую пересекает мост 2 и 6) — 3 ? Нет, это сложно.

Давайте использовать классическую схему Кёнигсберга, которую решал Эйлер.

Участки суши (вершины):

N1: берег справа (АЛЬШТАДТ)

N2: остров Кнайпхоф

N3: берег слева (ЛЕБЕНИХТ)

N4: остров Ломзее

Мосты (рёбра):

• Мост 1 (Лавочный): N1 — N2
• Мост 5 (Зелёный): N1 — N2
• Мост 2 (Кузнечный): N1 — N3
• Мост 6 (Потроховый): N2 — N3
• Мост 3 (Медовый): N2 — N4
• Мост 7 (Высокий): N3 — N4
• Мост 4 (Деревянный): N3 — N2 (связывает Лебенихт с Кнайпхофом)

Теперь посчитаем степени вершин:

• N1 (АЛЬШТАДТ): мосты 1, 5, 2. Степень = 3 (нечётная).
• N2 (О. КНАЙПХОФ): мосты 1, 5, 6, 3, 4. Степень = 5 (нечётная).
• N3 (ЛЕБЕНИХТ): мосты 2, 6, 7. Степень = 3 (нечётная).
• N4 (О. ЛОМЗЕЕ): мосты 3, 7. Степень = 2 (чётная).

Итого имеем: 3 вершины с нечётной степенью (N1, N2, N3) и 1 вершина с чётной степенью (N4).

Вывод:

Поскольку в графе существуют 3 вершины с нечётной степенью, пройти по всем мостам ровно один раз и вернуться в исходную точку (Эйлеров цикл) невозможно. Также невозможно пройти по всем мостам ровно один раз, закончив в другой точке (Эйлеров путь), потому что для Эйлерова пути должно быть максимум две вершины с нечётной степенью.

Ответ: Нет, построить такой маршрут невозможно, потому что есть более двух участков суши, к которым подходит нечётное число мостов (3 участка с нечётной степенью).