Главная → Уроки → Вероятность и статистика 7 класс

§ 21. Задача о Кёнигсбергских мостах, эйлеровы пути и эйлеровы графы

Прочитай параграф о знаменитой задаче про семь кёнигсбергских мостов: почему у промежуточной вершины степень чётная, что такое эйлеров путь и эйлеров граф, как теорема Эйлера по степеням вершин отвечает «можно» или «нельзя» и откуда берётся правило «нечётных вершин не больше двух», — а затем ответь на 10 вопросов.

В старом Кёнигсберге (теперь это Калининград) река Прегель делила город на четыре части: северный берег, южный берег и два острова — Кнайпхоф и Ломзе. Части города связывали семь мостов (рис. 1). Горожане развлекались задачей: пройти город насквозь так, чтобы на каждом мосту побывать ровно один раз. Легенда обещала удачу тому, у кого получится. Пробовали многие, не вышло ни у кого.

План старого Кёнигсберга: река Прегель течёт поперёк рисунка, сверху северный берег (участок А), снизу южный берег (участок В), посередине реки два острова — Кнайпхоф (участок Б) и Ломзе (участок Г). Через реку перекинуты семь мостов с номерами: мосты 1 и 2 ведут с северного берега на Кнайпхоф, мосты 3 и 4 — с южного берега на Кнайпхоф, мост 5 — с северного берега на Ломзе, мост 6 — с южного берега на Ломзе, мост 7 соединяет два острова
Рис. 1. План старого Кёнигсберга: четыре участка суши и семь мостов

Нитка вместо карандаша

Отложим на время мосты и возьмём любой связный граф. Представь, что мы не чертим его карандашом, а выкладываем ниткой. В промежуточную вершину нитка входит и тут же выходит — забирает сразу пару рёбер. Сколько раз нитка зашла, столько раз и вышла, поэтому рёбер у промежуточной вершины чётное число.

Особых вершин только две: та, где нитка началась, и та, где кончилась. У каждой из них одно ребро остаётся без пары, значит, степень нечётна. А если нитка вернулась туда, откуда вышла, нечётных вершин не будет вовсе.

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

Три графа рядом. Граф а) — квадрат 1—2—3—4 с диагональю 1—3, пять рёбер; степени вершин 3, 2, 3, 2, нечётных вершин две, весь граф обведён одной зелёной ниткой. Граф б) — два треугольника с общей вершиной 3, шесть рёбер; степени 2, 2, 4, 2, 2, нечётных вершин нет, зелёная нитка одна и замкнутая. Граф в) — треугольник 1—2—3 с вершиной 4 в центре, соединённой со всеми тремя углами, шесть рёбер; степень каждой вершины 3, нечётных вершин четыре, и граф выложен двумя нитками — синей и оранжевой
Рис. 2. Три графа из ниток: две нечётные вершины, ни одной, четыре

На рисунке 2 три графа. У первого нечётные вершины две — нитка одна, её концы как раз в этих вершинах.

Дальше — в приложении

Полный пересказ по учебнику «Вероятность и статистика 7 класс», тест из большого пула вопросов и разбор ошибок с ИИ-репетитором. За сданный тест ребёнок получает экранное время — родители задают, сколько минут стоит урок.

Пройти урок бесплатноКак это работает

Вопросы из теста

Правильные ответы и разбор ошибок — в приложении: при пересдаче вопросы меняются, поэтому списать не получится.

Какой путь называют эйлеровым?

Посмотри на граф кёнигсбергских мостов. Чему равна степень вершины Б — острова Кнайпхоф?

← § 20. Пути в графе. Связные графы§ 22. Утверждения и высказывания →