Условие:
11 На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она закончила его обводить в вершине B ?
\square
Ответ:
Решение:
Чтобы определить, с какой вершины Марта начала обводить граф, если она закончила в вершине B, нужно использовать свойства графов и теорию Эйлера.
- Определение четных и нечетных вершин: В графе, чтобы пройти по всем рёбрам, не поднимая карандаш и не проходя по одному ребру дважды, необходимо, чтобы:
- Все вершины имели четную степень (входящие и исходящие рёбра).
- Либо ровно две вершины ...