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

Решение:

Эта задача является классическим примером теории графов, известной как "Задача о Кёнигсберских мостах", решённой Леонардом Эйлером. Для решения этой задачи представим части города как вершины графа, а мосты — как рёбра, соединяющие эти вершины.

1. Определим вершины и рёбра:
   • Вершины (острова и берега):
     • о. Кнайпхоф (вершина)
     • о. Ломзее (вершина)
     • Альштадт (регион, одна вершина)
     • Лебенихт (регион, одна вершина)
   • Рёбра (мосты):
     • Кузнечный мост (соединяет о. Кнайпхоф и Лебенихт)
     • Деревянный мост (соединяет о. Ломзее и Лебенихт)
     • Медовый мост (соединяет о. Кнайпхоф и о. Ломзее)
     • Лавочный мост (соединяет Альштадт и о. Кнайпхоф)
     • Зелёный мост (соединяет Альштадт и о. Кнайпхоф)
     • Потроховый мост (соединяет Альштадт и о. Кнайпхоф)
     • Высокий мост (соединяет о. Ломзее и Альштадт)
2. Проверим степени вершин:
   • о. Кнайпхоф: соединен 4 мостами (Кузнечный, Медовый, Лавочный, Зелёный, Потроховый - обратите внимание, что на схеме Лавочный, Зелёный и Потроховый мосты ведут к Альштадту, но соединяют разные части Альштадта или острова с Альштадтом. По условию задачи, мосты соединяли части города. На схеме видно, что Лавочный, Зелёный и Потроховый мосты идут от о. Кнайпхоф к Альштадту, поэтому степень о. Кнайпхоф = 4 (Кузнечный + Медовый + 3 моста к Альштадту).
   • о. Ломзее: соединен 3 мостами (Медовый, Деревянный, Высокий).
   • Альштадт: соединен 4 мостами (Лавочный, Зелёный, Потроховый, Высокий).
   • Лебенихт: соединен 2 мостами (Кузнечный, Деревянный).
3. Применим теорему Эйлера: Эйлер доказал, что для того, чтобы можно было пройти по всем мостам ровно один раз (то есть построить Эйлеров путь или Эйлеров цикл), в графе должно быть либо 0 вершин с нечётной степенью (для Эйлерова цикла), либо ровно 2 вершины с нечётной степенью (для Эйлерова пути).
   • В нашем случае степени вершин: 4, 3, 4, 2.
   • Мы видим, что вершины о. Ломзее (степень 3) и Альштадт (степень 4, но на самом деле 3 моста ведут к острову Кнайпхоф, а один мост 'Высокий' ведет к Ломзее. По схеме, к Альштадту ведут 3 моста от Кнайпхоф и 1 мост от Ломзее. Итак, у Альштадта степень 4.)

   Пересчитаем степени вершин строго по схеме:

   Остров Кнайпхоф: мосты 1 (Лавочный), 2 (Кузнечный, но он ведёт к Лебенихту), 3 (Медовый), 5 (Зелёный), 6 (Потроховый). На схеме мост №2 (Кузнечный) соединяет о. Кнайпхоф и Лебенихт. Мост №3 (Медовый) соединяет о. Кнайпхоф и о. Ломзее. Мосты 1, 5, 6 соединяют о. Кнайпхоф с Альштадтом. Мост №7 (Высокий) соединяет о. Ломзее с Альштадтом. Мост №4 (Деревянный) соединяет о. Ломзее с Лебенихтом.

   Правильные степени вершин:

   • о. Кнайпхоф: 4 (мосты 1, 3, 5, 6)
   • о. Ломзее: 3 (мосты 3, 4, 7)
   • Альштадт: 4 (мосты 1, 5, 6, 7)
   • Лебенихт: 2 (мосты 2, 4)

   Итак, степени вершин: 4, 3, 4, 2.

   Вывод: У нас есть две вершины с нечётной степенью: о. Ломзее (3) и Альштадт (4 - тут ошибка, смотрим схему внимательно). Давайте ещё раз:

   Остров Кнайпхоф: Соединение с Лавочным (1), Медовым (3), Зелёным (5), Потроховым (6). Степень = 4.

   Остров Ломзее: Соединение с Медовым (3), Деревянным (4), Высоким (7). Степень = 3.

   Альштадт: Соединение с Лавочным (1), Зелёным (5), Потроховым (6), Высоким (7). Степень = 4.

   Лебенихт: Соединение с Кузнечным (2), Деревянным (4). Степень = 2.

   Степени вершин: 4, 3, 4, 2.

   Повторная проверка:

   1. О. Кнайпхоф: 1, 3, 5, 6 (4 моста) -> степень 4

   2. Лебенихт: 2, 4 (2 моста) -> степень 2

   3. О. Ломзее: 3, 4, 7 (3 моста) -> степень 3

   4. Альштадт: 1, 5, 6, 7 (4 моста) -> степень 4

   Итак, у нас есть 4 вершины: 4, 2, 3, 4.

   Одна вершина имеет нечетную степень (о. Ломзее, степень 3).

   По теореме Эйлера, если число вершин с нечетной степенью больше 2, то такого пути не существует.

   В оригинальной задаче Кёнигсберга было 4 острова/берега, и степени их были: 5, 3, 3, 3. Все 4 вершины имели нечетную степень.

   В данном конкретном рисунке, если мы интерпретируем как есть, то имеем вершины с степенями 4, 2, 3, 4. Только одна вершина (о. Ломзее) имеет нечетную степень. Это не соответствует условиям для существования Эйлерова пути или цикла.

   Однако, если трактовать задачу по рисунку, где мосты обозначены цифрами, а не названиями, то:

   Регионы: А (Альштадт), К (Кнайпхоф), Л (Лебенихт), М (Ломзее).

   Мосты: 1, 2, 3, 4, 5, 6, 7.

   1 (Лавочный): А - К

   2 (Кузнечный): К - Л

   3 (Медовый): К - М

   4 (Деревянный): М - Л

   5 (Зелёный): А - К

   6 (Потроховый): А - К

   7 (Высокий): А - М

   Степени:

   А: 1, 5, 6, 7 (4 моста) -> степень 4

   К: 1, 2, 3, 5, 6 (5 мостов) -> степень 5

   Л: 2, 4 (2 моста) -> степень 2

   М: 3, 4, 7 (3 моста) -> степень 3

   Степени вершин: 4, 5, 2, 3.

   У нас есть две вершины с нечётной степенью: К (5) и М (3).

   Согласно теореме Эйлера, если в графе ровно две вершины имеют нечётную степень, то существует Эйлеров путь, который начинается в одной из этих вершин и заканчивается в другой.

   Следовательно, пройти по всем мостам ровно один раз возможно.

   Пример такого маршрута: Начнём с острова Ломзее (М), так как у него степень 3.

   1. М -> 3 -> К (остров Кнайпхоф)
   2. К -> 5 -> А (Альштадт)
   3. А -> 7 -> М (остров Ломзее)
   4. М -> 4 -> Л (Лебенихт)
   5. Л -> 2 -> К (остров Кнайпхоф)
   6. К -> 1 -> А (Альштадт)
   7. А -> 6 -> К (остров Кнайпхоф)

   Мы прошли по всем 7 мостам ровно один раз. Маршрут: М - 3 - К - 5 - А - 7 - М - 4 - Л - 2 - К - 1 - А - 6 - К.

   Финальный маршрут: М (3) К (5) А (7) М (4) Л (2) К (1) А (6) К.

   Перепроверим:

   М - 3 -> К

   К - 5 -> А

   А - 7 -> М

   М - 4 -> Л

   Л - 2 -> К

   К - 1 -> А

   А - 6 -> К

   Все 7 мостов пройдены. Начали с М (степень 3) и закончили в К (степень 5).

   Финальный ответ:

   Да, можно построить такой маршрут, потому что в графе ровно две вершины (остров Ломзее и остров Кнайпхоф) имеют нечётную степень (3 и 5 соответственно).

   Пример маршрута: Ломзее → Медовый мост → Кнайпхоф → Зелёный мост → Альштадт → Высокий мост → Ломзее → Деревянный мост → Лебенихт → Кузнечный мост → Кнайпхоф → Лавочный мост → Альштадт → Потроховый мост → Кнайпхоф.