Чтобы обвести граф, не отрывая карандаша и не проводя по одному ребру дважды, нужно использовать путь Эйлера — путь, который проходит через каждое ребро ровно один раз. Условие задачи также указывает, что Пётр закончил обводить граф в вершине B.
Для существования такого пути граф должен иметь ровно две вершины с нечётной степенью (количеством соединённых рёбер). Начать нужно с одной из них, а закончить в другой.
Давай посмотрим на степени вершин:
- Вершина 1: соединена с вершинами 2, 4, 5 (степень = 3).
- Вершина 2: соединена с вершинами 1, 3, 5 (степень = 3).
- Вершина 3: соединена с вершинами 2, 4, 6 (степень = 3).
- Вершина 4: соединена с вершинами 1, 3, 6 (степень = 3).
- Вершина 5: соединена с вершинами 1, 2, 6 (степень = 3).
- Вершина 6: соединена с вершинами 3, 4, 5, B (степень = 4).
- Вершина B: соединена с вершиной 6 (степень = 1).
Все вершины, кроме B, имеют нечётную степень, и только вершина B имеет чётную степень. Однако, поскольку Пётр закончил в вершине B, а мы знаем, что возможен только Эйлеров путь с нечётными степенями, необходимо найти ещё одну вершину с нечётной степенью (что требует, чтобы одна из перечисленных выше вершин имела чётную степень).
В этом графе только вершина B имеет чётную степень (1), поскольку она соединяется только с вершиной 6. Все остальные вершины имеют нечётную степень, что сообщает, что они могут быть отправными точками.
Вывод:
Поскольку вершина B — единственная чётная и конечная точка пути, а все другие — нечётные, Пётр начал обводить граф с любой из вершин, участвующих в соединении к B, не считая её. По общему принципу графов, наиболее вероятно он начал с одной из соседних вершин с B (например, вершина 6).
Теперь попробуем путь:
- Пётр начинает с точки 6 и следует по всем рёбрам, пока он не достигнет точки B.
Таким образом, вероятно начальной вершиной была вершина 6.
