На рисунке изображен граф. Николай обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Николай начал обводить граф, если…
На рисунке изображен граф. Николай обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Николай начал обводить граф, если он закончил его обводить в вершине M?
Чтобы определить, с какой вершины Николай начал обход графа, нужно понять, как проходить граф, не повторяя рёбра.
Для выполнения такого обхода, известного как "Эйлеров путь", необходимо знать следующее:
Эйлеров путь существует, если у графа ровно 0 или 2 вершины с нечетной степенью. Степень вершины — это количество рёбер, исходящих из неё.
Если в графе две вершины с нечетной степенью, то Эйлеров путь начинается в одной из этих вершин и заканчивается в другой.
Проанализируем граф:
- A: степень 3
- B: степень 5
- C: степень 3
- E: степень 3
- M: степень 3
- K: степень 3
- N: степень 3
- P: степень 2
- D: степень 4 (не изображена полностью на изображении, но предполагается, так как неявно соединяет E и B)
Так, имеем четыре вершины с нечетной степенью: A, B, C, E, M, K, N. Но M — это конечная точка.
Следовательно, на основании анализа с учётом предполагаемого полного графа, обход мог бы начаться на вершине, также имеющей нечётную степень.
Пути, которые Николай мог бы выбрать, чтобы закончить на M, начинаются с любой из нечётных, например, с вершины N, так как её степень нечётна.
Таким образом, Николай мог начать обводить граф с вершины N.
