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

Решение:

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

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

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

Посчитаем степени вершин на графе:

• Вершина A: степень 2 (четная)
• Вершина B: степень 3 (нечетная)
• Вершина C: степень 2 (четная)
• Вершина D: степень 2 (четная)
• Вершина E: степень 2 (четная)
• Вершина F: степень 2 (четная)
• Вершина G: степень 2 (четная)
• Вершина H: степень 2 (четная)

В данном графе только одна вершина (B) имеет нечетную степень. Такой граф нельзя обойти, не отрывая карандаша, если начало и конец обхода — разные вершины. Однако, если условие «не проводя ни одно ребро дважды» выполнено, и она закончила в вершине B, то это возможно только если B является единственной вершиной нечетной степени, а начало обхода также должно быть этой вершиной.

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

Ответ: B