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