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

Решение:

• Цель: Понять.

1. Для понимания данной задачи, нам необходимо вспомнить базовые понятия графовой теории.
2. Граф – это математическая структура, состоящая из вершин (узлов) и рёбер (связей между вершинами).
3. При обводе графа Ваня должен пройти через каждое ребро ровно один раз, не отрывая карандаша от бумаги и не проводя ни одно ребро дважды. Очевидно, что граф – это связный граф.

Теперь давайте рассмотрим способ решения задачи:

1. Вспомним теорему о связных графах:

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

2. Опять же, обратим внимание на условие задачи: Ваня начал обводить граф и закончил в вершине Е.

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

4. Следовательно, существует еще одна вершина с нечетной степенью – это и есть та вершина, с которой начал обводить Ваня.

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