30. На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она закончила его обводить в вершине D?

Анализ задачи

Задача нахождения начала и конца обхода графа без отрыва карандаша и без повторения ребер сводится к определению вершин с нечетной степенью (количеством ребер, подходящих к вершине). В графе, который можно обойти за один раз, может быть либо 0 вершин с нечетной степенью (если начало и конец совпадают), либо 2 вершины с нечетной степенью (начало и конец обхода).

Пошаговое решение:

1. Анализ графа: Граф состоит из двух пересекающихся окружностей. Вершины обозначены буквами A, B, C, D, E, F, G, H, K.
2. Определение степеней вершин:
   • Вершина A: степень 2 (ребра AG, AF)
   • Вершина B: степень 2 (ребра BG, BK)
   • Вершина C: степень 2 (ребра CH, CK)
   • Вершина D: степень 2 (ребра DK, DE)
   • Вершина E: степень 2 (ребра EK, ED)
   • Вершина F: степень 2 (ребра FA, FG)
   • Вершина G: степень 4 (ребра GA, GB, GH, GK)
   • Вершина H: степень 2 (ребра HG, HC)
   • Вершина K: степень 4 (ребра KB, KC, KE, KG)
3. Выявление вершин с нечетной степенью: В данном графе все вершины имеют четную степень (2 или 4). Это означает, что граф является эйлеровым, и его можно обойти, начав и закончив в одной и той же вершине, пройдя все ребра ровно один раз.
4. Условие задачи: Марта закончила обводить граф в вершине D. Поскольку все вершины имеют четную степень, Марта могла начать обход из любой вершины, включая D, и закончить в той же вершине D.

Ответ: Марта могла начать обводить граф из вершины D.