На рисунке изображён граф. Пётр обвел этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Пётр начал обводить граф, если он…
На рисунке изображён граф. Пётр обвел этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Пётр начал обводить граф, если он закончила его обводить в вершине 6 6? 5800_VPR8_13_510x350.svg
Для решения данной задачи мы можем воспользоваться правилом о нечетных степенях вершин.
Вершина графа увеличивает свою степень на 2 каждый раз, когда через нее проходит ребро. Чтобы обвести весь граф, каждая вершина, кроме начальной и конечной, должна иметь четную степень.
Так как граф является связным (есть путь между любой парой вершин), все вершины этого графа должны иметь степень, кратную двум, за исключением начальной и конечной вершин.
Исходя из правила нечетных степеней вершин, для графа, который нарисовал Пётр, возможны два варианта:
Пётр начал обводить граф из вершины 1 или 3, так как они имеют нечетные степени (3 и 1 соответственно).
Пётр мог начать обводить граф из вершины 1, так как каждая вершина графа, кроме начальной и конечной, должна иметь четную степень.
Исходя из того, что Пётр закончил обводить граф в вершине 6, оптимальным выбором будет вершина 1.
Таким образом, можно предположить, что Пётр начал обводить граф, начиная с вершины 1.
