Задача 31093

Темы:    [ Степень вершины ] [ Обход графов ] [ Четность и нечетность ]

Сложность: 3+ Классы: 6,7,8

Условие

Существует ли ломаная, пересекающая все рёбра картинки по одному разу?

Решение

Рассмотрим граф, вершины которого соответствуют шести областям, на которые "картинка" разбивает плоскость (пять прямоугольников и внешняя область), а рёбра – разделяющим эти обзасти отрезкам. Построив ломаную, мы провели бы в этом графе эйлеров путь. Но в графе три нечётных вершины (степени 5, 5 и 9), поэтому в нем нет эйлерова пути (см. задачу 31095 а).

Ответ

Не существует.

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	25