Упражнение 6 из 10 Сообщить об ошибке На рисунке изображён граф. Николай обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой…
Упражнение 6 из 10 Сообщить об ошибке На рисунке изображён граф. Николай обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Николай начал обводить граф, если он закончил его обводить в вершине A A?
Для решения этой задачи, давайте взглянем на основное свойство связного графа.
По определению, если граф является связным (то есть между любыми двумя вершинами существует путь), то у каждой вершины кроме двух будут четно количество рёбер. А у двух вершин — нечётное количество рёбер.
Так как Николай обвёл граф, не отрывая карандаша от листа бумаги и не проходя по ребру дважды, то каждая вершина должна содержать четное количество инцидентных рёбер, за исключением начальной и конечной вершин.
Исходя из этого, если он закончил обводить граф в вершине А, то Николай начал с вершины, у которой нечётное количество инцидентных рёбер, то есть с вершины, которая является начальной или конечной.
Таким образом, Николай начал обводить граф с вершины, отличной от вершины А, у которой было нечётное количество инцидентных рёбер.
