Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 92, §21*
№146. Пять участков отделены друг от друга заборами (см. план на рис. 40). Можно ли побывать на каждом участке, но при этом перелезть через каждый забор ровно один раз?
Дано:
пять участков; план — на рисунке 40
Найти:
можно ли побывать на каждом участке, перелезая через каждый забор ровно один раз
Построим граф: участки — вершины, а каждый забор — ребро между участками, которые он разделяет. Тогда нужно пройти по графу путь, который проходит по каждому ребру ровно один раз — то есть эйлеров путь (п. 21). Он существует, если граф связный и вершин нечётной степени не больше двух. Обозначим участки буквами: А — верхний, Б — малый слева, В — малый справа, Г — большой слева, Д — большой справа.
На плане забором выглядит каждая нарисованная линия — не только перегородки между участками, но и внешняя граница плана. За внешней границей — «внешняя территория» (вне плана), которую тоже считаем вершиной графа: через внешний забор можно перелезть, выйдя с участка наружу. Всего заборов 14: 7 между участками и 7 по краю плана (по одному у А, Б, В и по два у Г и Д).
| Участок | Заборов с соседними участками | Заборов по краю плана | Всего заборов (степень вершины) |
|---|---|---|---|
| А | 4 | 1 | 5 |
| Б | 2 | 1 | 3 |
| В | 2 | 1 | 3 |
| Г | 3 | 2 | 5 |
| Д | 3 | 2 | 5 |
| вне плана | 0 | 7 | 7 |
Степени вершин: 5, 3, 3, 5, 5 и 7 — все шесть чисел нечётные. Нечётных вершин больше двух, поэтому эйлерова пути нет: пройти по всем заборам по одному разу нельзя. Ответ: нет.
Замечание. Если считать заборами только перегородки между пятью участками (внешнюю границу не считать), то степени участков такие: А — 4, Б — 2, В — 2, Г — 3, Д — 3. Нечётных вершин две (Г и Д), граф связный — тогда путь по всем семи перегородкам есть, например Г → Б → А → В → Д → А → Г → Д (на рисунке справа он пронумерован). Ответ учебника «Нет» соответствует первому пониманию — когда перелезть нужно и через все наружные заборы.
Ответ: Нет. Если считать заборами все линии плана (и внешний край), то в графе заборов шесть вершин нечётной степени (5, 3, 3, 5, 5 и 7) — эйлерова пути нет. (При заборах только между участками путь есть — см. замечание.)
