На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она…
На рисунке изображён граф. Марта обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. С какой вершины Марта начала обводить граф, если она закончила его обводить в вершине К
Понимание задачи:
Марта обвела граф, не отрывая карандаша от листа бумаги и не проводя ни одно ребро дважды. Значит, это задача о поиске эйлерова цикла — пути, который проходит по каждому ребру графа ровно один раз и возвращается в исходную вершину.
Решение:
Чтобы определить, с какой вершины Марта начала обводить граф, необходимо рассмотреть степени вершин графа. Степень вершины - количество инцидентных ей рёбер.
Поскольку Марта обошла каждое ребро, потребуется, чтобы все вершины графа были чётной степени (за исключением, возможно, двух вершин, если это направленный граф).
Поскольку она закончила в вершине К и вершина К имеет нечётную степень, значит, Марта начала свой путь в какой-то другой вершине.
Это можно понять из теоремы Эйлера: граф содержит эйлеров цикл тогда и только тогда, когда у него нет вершин нечётной степени или их количество чётно и равно 2.
Поэтому, вершина, в которую Марта начала обводить граф, обладает нечётной степенью.
Таким образом, если вершина K имеет нечётную степень и является концом цикла (последней вершиной), Марта начала обводить граф из вершины, не являющейся вершиной K.
