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

Для решения этой задачи необходимо определить, с какой вершины можно начать обход графа, чтобы закончить в вершине B, при этом не отрывая карандаша от бумаги и не проводя ни одно ребро дважды. Это задача на эйлеров путь. В графе должны быть только две вершины с нечетной степенью (количеством ребер, выходящих из вершины) — начало и конец пути. Если все вершины имеют четную степень, то можно начинать с любой вершины и закончить в ней же. Подсчитаем степени вершин графа: A: 3 B: 3 C: 2 D: 2 E: 2 F: 2 G: 3 H: 3 Таким образом, у нас 4 вершины с нечетной степенью: A, B, G, H. Для того, чтобы закончить обход в вершине B, начать нужно в вершине A, G или H. Проверим один из возможных путей. Например, начнем с вершины H: H-A-B-C-D-E-F-G-H-G-A-B Указанный путь заканчивается в вершине B, начинаясь в вершине H. Значит, ответ: H. Ответ: H