3. На рисунке изображен граф. Петя обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Петя начал обводить граф, если он закончил его обводить в вершине Е?

Question

Вопрос:

Фото задания: 3. На рисунке изображен граф. Петя обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру…

3. На рисунке изображен граф. Петя обвёл этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одному ребру дважды. С какой вершины Петя начал обводить граф, если он закончил его обводить в вершине Е?

Accepted Answer

Краткое пояснение:

Краткое пояснение: Если граф можно обойти, не отрывая карандаша и не проводя по одному ребру дважды, то количество вершин с нечетной степенью должно быть равно 0 (если начало и конец совпадают) или 2 (если начало и конец в разных вершинах). Начальная вершина в случае Эйлерова пути - одна из вершин с нечетной степенью.

Пошаговое решение:

Определим степени вершин на рисунке:

A: степень 2
B: степень 2
C: степень 4
D: степень 4
E: степень 2
F: степень 2
G: степень 2
H: степень 2

Все вершины на рисунке имеют четную степень. Это означает, что существует Эйлеров цикл (граф можно обойти, начав и закончив в одной и той же вершине).

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

Ответ: E