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

Решение:

Задача описывает обход графа без отрыва карандаша и без повторного проведения ребер. Это возможно, если граф является Эйлеровым или полу-Эйлеровым.

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

Полу-Эйлеров граф (в котором можно пройти по всем ребрам ровно один раз, но начать и закончить в разных вершинах) существует тогда и только тогда, когда граф имеет ровно две вершины нечетной степени. В этом случае начало и конец обхода совпадают с этими вершинами.

Давайте определим степени вершин на рисунке:

• Вершина A: степень 4 (четная)
• Вершина B: степень 4 (четная)
• Вершина C: степень 4 (четная)
• Вершина D: степень 4 (четная)
• Вершина E: степень 4 (четная)
• Вершина F: степень 4 (четная)
• Вершина G: степень 4 (четная)
• Вершина H: степень 4 (четная)
• Вершина I: степень 4 (четная)
• Вершина J: степень 4 (четная)
• Вершина K: степень 4 (четная)
• Вершина L: степень 4 (четная)

В данном графе все вершины имеют четную степень. Следовательно, это Эйлеров граф. В Эйлеровом графе можно начать обход из любой вершины и закончить в ней же.

Однако, условие задачи гласит, что Марта закончила обводить граф в вершине D. Это означает, что она должна была начать обход из той же вершины, из которой закончила, если бы граф был действительно Эйлеровым и ей нужно было бы вернуться в исходную точку. Но если она закончила в D, и все вершины имеют четную степень, это подразумевает, что D является одновременно и начальной вершиной, если бы путь был замкнутым. Но если она начала из другой вершины и закончила в D, это возможно, если граф является полу-Эйлеровым, где две вершины имеют нечетную степень. В нашем случае все вершины имеют четную степень.

Если все вершины имеют четную степень, то обход является замкнутым, то есть начальная и конечная вершины совпадают. Поскольку Марта закончила в вершине D, она должна была начать с той же вершины.

Ответ: D.