Вопрос:

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

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

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

Чтобы определить, с какой вершины Ваня начал обводить граф, воспользуемся теорией Эйлеровых путей. Граф можно нарисовать, не отрывая карандаша и не проходя по ребрам дважды, только если в нём не более двух нечётных вершин (вершин, из которых выходит нечётное количество линий). 1. Посчитаем степень каждой вершины (количество выходящих линий): - Вершина $A$: 2 (чётная) - Вершина $B$: 3 (нечётная) - Вершина $C$: 3 (нечётная) - Вершина $D$: 2 (чётная) - Вершина $E$: 2 (чётная) - Вершина $F$: 2 (чётная) - Вершина $G$: 2 (чётная) - Вершина $H$: 2 (чётная) - Вершина $K$: 2 (чётная) - Вершина $L$: 2 (чётная) - Вершина $M$: 2 (чётная) - Вершина $N$: 2 (чётная) - Вершина $O$: 6 (чётная) 2. В этом графе ровно две нечётные вершины: $B$ и $C$. Согласно правилу, если Эйлеров путь существует и в графе есть нечётные вершины, то путь должен начинаться в одной нечётной вершине, а заканчиваться в другой. 3. По условию Ваня закончил обводить граф в вершине $C$. Следовательно, начать он должен был в другой нечётной вершине — $B$. **Ответ: B**

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

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