6. Тип 11 № 8737 На рисунке изображён граф. Катя обвела этот граф, не отрывая карандаша от листа бума- ги и не проводя ни одно ребро дважды. Начала она в вершине С. В какой вершине Катя за- кончила обводить граф?

Решение:

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

В данном графе вершины имеют следующие степени:

• A: 1
• B: 3
• C: 4
• D: 3
• E: 4
• F: 3
• H: 3
• K: 2
• L: 2
• M: 1
• N: 1

Вершины A, B, D, F, H, M и N имеют нечётную степень. Так как Катя начала в вершине C (чётная степень), а нужно закончить в вершине с нечётной степенью, то она могла закончить в любой из вершин A, B, D, F, H, M и N.

После анализа схемы графа, можно сказать, что Катя начала в вершине C и закончила в вершине E.

Попробуем пройти по графу, начиная с вершины С, не отрывая карандаша и не проходя по одному ребру дважды:

• C - L
• L - M
• M - N
• N - B
• B - A
• A - F
• F - H
• H - K
• K - L
• L - E
• E - D
• D - F

Проходя по графу таким образом, можно предположить, что Катя начала в вершине С и закончила в вершине Е

Ответ: E

Проверка за 10 секунд: Убедись, что правильно посчитал степень каждой вершины и нашёл вершину, в которой нужно закончить обход графа.

Запомни: Если граф имеет две вершины с нечётной степенью, то обход нужно начинать в одной из этих вершин и заканчивать в другой.