Вопрос:

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

Фотография

Ответ ассистента

Для решения этой задачи нужно вспомнить правила теории графов, касающиеся Эйлеровых путей. Граф можно «обойти» без отрыва карандаша, если количество вершин с нечетной степенью равно 0 или 2: 1. Степень вершины — это количество рёбер, выходящих из неё. - Вершина 1: 2 ребра (степень 2 — четная) - Вершина 2: 2 ребра (степень 2 — четная) - Вершина 3: 2 ребра (степень 2 — четная) - Вершина 4: 2 ребра (степень 2 — четная) - Вершина 5: 6 рёбер (степень 6 — четная) - Вершина 6: 2 ребра (степень 2 — четная) - Вершина 7: 3 ребра (степень 3 — нечетная) - Вершина 8: 3 ребра (степень 3 — нечетная) 2. Так как в графе ровно две вершины с нечетной степенью (7 и 8), это значит, что у графа есть Эйлеров путь. Такой путь всегда начинается в одной нечетной вершине и заканчивается в другой. 3. Если Олег начал обводить граф в вершине 8, значит, он обязательно должен закончить свой путь в другой нечетной вершине — вершине 7. **Ответ: 7**

Другие решения

Что ещё задавали пользователи