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