Задачи в стиле «Мостики Кёнигсберга»

Задачи в стиле «Мостики Кёнигсберга» — это классика теории графов и задач на один росчерк.

Суть оригинальной задачи (1736 год)

Город Кёнигсберг (ныне Калининград) был расположен на двух берегах реки Преголя и двух островах. Острова соединялись с берегами и между собой семью мостами.

Вопрос: Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз и вернувшись в начальную точку?

Модель Эйлера

Эйлер представил задачу как граф:

· Вершины — части суши (2 берега, 2 острова → 4 вершины).

· Рёбра — мосты (7 рёбер).

Граф получился таким:

A (северный берег)

/|\

/ | \

B | C

\ | / \

\|/ \

D ?

На самом деле точная схема связей:

Северный берег (A)

| 1

Остров (B)

/ \ \

2/ \3 \4

/ \ \

Южный берег (C) Остров (D)

\5 6/ /7

\ / /

\ / /

(D?)

Правильнее так:

Было 4 района:

1. Северный берег (A)

2. Южный берег (B)

3. Остров Кнайпхоф (C)

4. Остров Ломзе (D)

Мосты:

1. A–C

2. A–C (второй мост)

3. A–B

4. B–C

5. B–D

6. B–D (второй мост)

7. C–D

Степени вершин:

A: 3 моста (1,2,3)

B: 5 мостов (3,4,5,6,? на самом деле B соединён с A,C,D) — уточним ниже.

Давай построим точно:

Точная схема мостов (историческая):

A

|\

| \

C--B

| |\

| | \

D--+--?

Лучше список рёбер (мостов):

1. A–C

2. A–C (ещё один)

3. A–B

4. B–C

5. B–D

6. B–D (ещё один)

7. C–D

Подсчитаем степени:

· A: соединён с C (2 раза) и с B (1 раз) → степень 3 (нечётная)

· B: соединён с A (1), с C (1), с D (2 раза) → степень 4 (чётная)?? Стоп, проверяем: у B связи: AB(1), BC(1), BD(2) → всего 4. Да, чётная.

· C: соединён с A (2), с B (1), с D (1) → степень 4 (чётная)

· D: соединён с B (2), с C (1) → степень 3 (нечётная)

Нечётные вершины: A и D (2 штуки).

Вывод Эйлера:

Чтобы пройти по всем мостам по разу с возвратом в начало, нужно 0 нечётных вершин.

Чтобы пройти по всем мостам по разу без обязательного возврата, нужно 2 нечётных вершины (начало и конец).

Здесь нечётных вершин 2 → можно пройти, но начать и закончить в разных местах (в A и D).

Но! Исторически Эйлер получил 4 нечётные вершины? Это известный момент: в старых описаниях степени были: A=3, B=5, C=3, D=3 — итого 4 нечётные → нельзя вообще.

Видимо, в реальном Кёнигсберге было другое распределение. В классической учебной задаче говорят: нельзя (ни с возвратом, ни без), потому что нечётных вершин 4.

Типовые задачи «в стиле Кёнигсберга»

Задача 1

На рисунке показаны острова и мосты. Можно ли обойти все мосты по одному разу?

*A

/ \

/ \

B*---*C

| \ / |

| *D |

| / \ |

*E *F

(Здесь рёбра — мосты, вершины — земли)

Решение:

Считаем степени:

A=2, B=3, C=3, D=4, E=2, F=2

Нечётные: B и C (2 шт) → можно, начав в B и закончив в C (или наоборот).

Задача 2 (с лишним мостом)

Допустим, в Кёнигсберге построили восьмой мост между A и D. Можно ли тогда обойти все мосты по одному разу и вернуться в начало?

Решение:

Добавляем ребро A–D:

A было 3 → станет 4 (чётная)

D было 3 → станет 4 (чётная)

B=5, C=3 (в классическом счёте) — но если взять наш ранний подсчёт (A=3,B=4,C=4,D=3), то:

A: 3→4 (чёт)

D: 3→4 (чёт)

B=4, C=4

Все вершины чётные! → Можно, начиная с любого района и возвращаясь в него.

Задача 3 (современная)

В парке есть 4 площадки, соединёнными дорожками-мостиками через ручьи:

· Площадка P соединена с Q (2 дорожки), с R (1 дорожка)

· Q соединена с R (2 дорожки), с S (1 дорожка)

· R соединена с S (1 дорожка)

· S соединена с P (1 дорожка)

Можно ли пройти все дорожки по разу, не отрывая карандаж?

Решение:

Строим граф:

P: PQ(2), PR(1), SP(1) → степень 4

Q: PQ(2), QR(2), QS(1) → степень 5 (нечётная)

R: PR(1), QR(2), RS(1) → степень 4

S: QS(1), RS(1), SP(1) → степень 3 (нечётная)

Нечётные: Q и S (2 шт) → можно, начав в Q и закончив в S.

Общий алгоритм решения таких задач

1. Определи вершины — участки суши (острова, берега).

2. Определи рёбра — мосты (каждый мост — одно ребро, даже если между теми же участками два моста — это два параллельных ребра).

3. Посчитай степень каждой вершины — сколько мостов к ней ведёт.

4. Примени правило:

· 0 нечётных — маршрут замкнутый (можно начать и закончить где угодно).

· 2 нечётных — маршрут незамкнутый (начинать в одной нечётной, закончить в другой).

· 4 или более нечётных — маршрут невозможен.

5. Если можно, построй маршрут, следя, чтобы не отрезать себя от непройденных мостов.

Практическое задание

Попробуй решить:

«На острове есть 3 озера, из каждого вытекает по 3 реки в море. Можно ли совершить путешествие, переплыв каждую реку ровно один раз? (Берега — морской берег и берега озёр — разные вершины, реки — рёбра)»

Схема:

Море (M)

/ | \

L1 L2 L3 (озёра)

| | |

? ? ?

Каждое озеро соединено с морем 3 реками. Других соединений нет.

Считаем степени:

M: 9 рек → нечётная? 9 — нечётная.

L1: 3 реки → нечётная.

L2: 3 реки → нечётная.

L3: 3 реки → нечётная.

Всего 4 нечётные вершины → нельзя.