Назад
Задача

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

Решение

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

Ответ

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

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет