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

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

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

Не понял параграф? Бесплатный ИИ-репетитор по вероятности и статистике 7 класс объяснит по шагам, но готовый ответ не скажет.

Спросить репетитора

В старом Кёнигсберге (теперь это Калининград) река Прегель делила город на четыре части: северный берег, южный берег и два острова — Кнайпхоф и Ломзе. Части города связывали семь мостов (рис. 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 три графа. У первого нечётные вершины две — нитка одна, её концы как раз в этих вершинах.

Хочешь больше времени в телефоне?

В Family Track телефон открывается за уроки: прочитал параграф, сдал тест и получил минуты. Сколько минут стоит урок, решают родители. Отправь им ссылку, пусть посмотрят.

Отправить родителямПройти урок бесплатно

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

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

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

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

Не получается разобраться? Бесплатный ИИ-репетитор по вероятности и статистике 7 класс разберёт ошибку по шагам и не даст списать.

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