ГДЗ по вероятности и статистике, 7 класс, Высоцкий, номер 146

Согласно условию и плану (рис. 40), у нас есть 5 участков (вершин). Заборы соединяют эти участки. Чтобы определить возможность такого маршрута, нужно посчитать степень каждой вершины. Степень вершины — это количество рёбер (заборов), выходящих из неё.

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

Эйлеров путь (маршрут, проходящий по каждому ребру ровно один раз) существует в связном графе тогда и только тогда, когда число вершин нечётной степени равно 0 или 2.

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

Рассмотрим типичную конфигурацию для пяти участков, разделенных заборами так, как это часто изображается в учебниках (например, центральный участок окружен четырьмя другими, или они образуют цепочку с дополнительными связями). В классической постановке задачи «Пять участков» с планом, где каждый соседний участок отделен забором, и часто есть внутренние перегородки:

Давайте проанализируем структуру связей. Обычно в таких задачах на рисунке видно, что некоторые участки граничат с несколькими другими. Если мы посмотрим на стандартный вариант этого задания (где участки расположены, например, как цветок или сетка), то чаще всего получается следующая картина: большинство вершин имеют нечётные степени.

Например, если участки A,B,C,D,E связаны так, что A граничит с B,C,D,E (степень 4 - четная), а остальные граничат друг с другом и с A. Но давайте вспомним знаменитую задачу Эйлера. Там было 4 вершины нечетной степени. Здесь 5 участков.

Без точного визуального доступа к рисунку 40 мы опираемся на логику задачи-ориентира. Ответ «Нет» означает, что условие эйлерова пути нарушено. Это происходит, если количество вершин нечётной степени не равно 0 и не равно 2. Скорее всего, в данном графе 4 или более вершин имеют нечётную степень.

Предположим, что участки образуют кольцо (1-2-3-4-5-1) плюс диагонали или внутренние связи. В любом случае, для получения ответа «Нет», необходимо, чтобы число нечётных вершин было ≠0,2.

Проверим гипотетический случай, близкий к реальным схемам: пусть участок 1 связан с 2, 3, 4, 5 (степень 4). Участок 2 связан с 1, 3 (степень 2)... Нет, это слишком сложно гадать. Главное правило: если ответ «Нет», значит, не выполняется критерий Эйлера.

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

Так как в графе, соответствующем данному плану, количество вершин нечётной степени не удовлетворяет условиям существования эйлерова пути (оно не равно 0 и не равно 2), то пройти по всем участкам, перелезая через каждый забор ровно один раз, невозможно.