ДОМАШНЕЕ ЗАДАНИЕ: ДМ7 стр. 155 №16 16. В городе пять островов (рис. 45), некоторые из которых соединены мостами. Можно ли обойти все острова, пройдя по каждому мосту ровню один раз? Решите та- кую же задачу для другого города, схема которого изображена на рисунке 46. (Задача такого типа про город Кенигсберг впервые была решена Леонардом Эйлером.) Рис. 45 Рис. 46

Ответ: Обойти все острова, пройдя по каждому мосту ровно один раз, нельзя ни для схемы на рисунке 45, ни для схемы на рисунке 46.

Решение:

• Анализ графа на рисунке 45:
• Верхний левый узел имеет степень 3 (нечётная).
• Верхний правый узел имеет степень 3 (нечётная).
• Нижний левый узел имеет степень 2 (чётная).
• Нижний правый узел имеет степень 2 (чётная).
• Верхний центральный узел имеет степень 2 (чётная).
• В графе на рисунке 45 две вершины с нечётной степенью. Следовательно, можно пройти по всем мостам ровно один раз, начав в одной из этих вершин и закончив в другой.
• Анализ графа на рисунке 46:
• Верхний левый узел имеет степень 3 (нечётная).
• Верхний правый узел имеет степень 3 (нечётная).
• Нижний левый узел имеет степень 3 (нечётная).
• Нижний правый узел имеет степень 3 (нечётная).
• Центральный узел имеет степень 4 (чётная).
• В графе на рисунке 46 четыре вершины с нечётной степенью. Следовательно, нельзя пройти по всем мостам ровно один раз.

Ответ: Обойти все острова, пройдя по каждому мосту ровно один раз, нельзя ни для схемы на рисунке 45, ни для схемы на рисунке 46.