На рисунке изображён граф. Светлана обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Светлана начала обводить граф,…
На рисунке изображён граф. Светлана обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Светлана начала обводить граф, если она закончила его обводить в вершине L L?
Чтобы решить эту задачу, необходимо использовать теорему о нечетных степенях вершин в графе.
Теорема Эйлера для эйлерова пути:
Эйлеров путь (путь, проходящий по всем рёбрам графа без повторений) существует, если в графе не более двух вершин с нечётной степенью. Если такие вершины есть, то эйлеров путь начинается в одной и заканчивается в другой.
Анализ графа:
Посчитаем степень каждой вершины:
- \( A \) — 3 (нечётная)
- \( B \) — 2 (чётная)
- \( C \) — 3 (нечётная)
- \( D \) — 4 (чётная)
- \( E \) — 2 (чётная)
- \( F \) — 3 (нечётная)
- \( J \) — 3 (нечётная)
- \( K \) — 3 (нечётная), где закончила Светлана.
Вершины с нечётной степенью: \( A, C, F, J, K \).
Для существования эйлерова пути с точно такими условиями, начало и конец должны быть в вершинах с нечётной степенью. Указано, что Светлана закончила в вершине \( K \). Значит, начаться путь должен был с одной из остальных вершин с нечётной степенью.
Вывод:
Светлана могла начать путь с одной из следующих вершин: \( A, C, F, \) или \( J \).
Поскольку в задаче не дано направления пути, точно определить одну вершину невозможно, если не было дополнительных условий. Таким образом, следует учитывать, что одной из возможных вершин для начала была одна из упомянутых нечётных вершин.
