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

Решение:

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

Теорема Эйлера:

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

Для решения задачи нужно определить степени всех вершин графа:

• Степень вершины A: 2 (рёбра AB, AH)
• Степень вершины B: 4 (рёбра BA, BC, BF, BH)
• Степень вершины C: 2 (рёбра CB, CD)
• Степень вершины D: 2 (рёбра DC, DE)
• Степень вершины E: 2 (рёбра ED, EF)
• Степень вершины F: 4 (рёбра FB, FE, FG)
• Степень вершины G: 2 (рёбра GF, GH)
• Степень вершины H: 2 (рёбра HA, HB, HG)

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

Так как Марта закончила обводить граф в вершине В, а в графе есть Эйлеров цикл, она могла начать обводить граф из любой вершины.

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