На рисунке изображён граф. Тимофей обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Тимофей начал обводить граф, если…
На рисунке изображён граф. Тимофей обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Тимофей начал обводить граф, если он закончил его обводить в вершине В?
Цель: Понять
Дано: на графе Тимофей обводил его, начиная с неопределенной вершины и заканчивая в вершине В.
Решение:
Когда мы обводим граф, из каждой вершины должно выходить четное количество рёбер (или 0, если это изолированная вершина). Это следует из того, что входное и исходящее количество рёбер из вершины должно быть одинаковым для того, чтобы можно было пройти по каждому ребру и вернуться в исходную вершину.
Поскольку Тимофей начал и закончил обводку в определенных вершинах, то все вершины графа, кроме начальной и конечной вершин, должны обладать степенью 2 (четным количеством инцидентных рёбер).
Поэтому, если мы рассмотрим вершину B, для которой степень равна 2, это означает, что Тимофей пришел в вершину B из другой вершины и должен отойти из вершины B в другую вершину.
Итак, Тимофей начал обводить граф из той вершины, из которой он пришёл в вершину B.
Ответ: Тимофей начал обводить граф из вершины, из которой он пришёл в вершину B.
