На рисунке изображён граф. Пётр обвел этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Пётр начал обводить граф, если он…
На рисунке изображён граф. Пётр обвел этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Пётр начал обводить граф, если он закончила его обводить в вершине 6? https://storage.yandexcloud.net/newschool-media-prod/chat-gpt/question/760bb23cae02459c994d74a779708564.jpeg
Для решения данной задачи по обводу графа без отрыва карандаша нужно использовать понятие степеней вершин.
В первую очередь, обратим внимание на количество рёбер, сходящихся в каждую вершину графа. Это количество называется степенью вершины.
Когда Пётр закончил обводить граф, он остановился в вершине 6. Значит, эта вершина имеет нечётную степень.
Теорема о сумме степеней вершин в графе (для неориентированных графов) гласит, что сумма степеней всех вершин равна удвоенному количеству рёбер.
Поскольку каждое ребро графа учитывается дважды (для вершины, входящей исходящее), то сумма степеней всех вершин равна удвоенному количеству рёбер. Таким образом, сумма всезе всех степеней вершин графа - это четное число.
Из пунктов 2 и 4 следует, что в графе должно быть четное число вершин со степенями, равными чётному числу, и нечётное число вершин со степенями, равными нечётному числу.
Так как вершина 6 имеет нечётную степень (конец обвода), значит, сумма степеней всех вершин графа - четное число и изначальная вершина обвода Петра также должна иметь нечётную степень.
Таким образом, можно сделать вывод, что Пётр начал обводить граф из вершины с нечётной степенью, чтобы закончить в вершине 6.
