ГДЗ 11 На рисунке изображён граф. Аня обвела этот граф, не отрывая карандаша от листа бумаги и не проводя ни по одном...

11

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

Решение:

Согласно теории графов, путь, проходящий по каждому ребру ровно один раз (эйлеров путь), возможен в связном графе тогда и только тогда, когда количество вершин с нечётной степенью (количеством выходящих из них рёбер) равно 0 или 2.

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

Определим степени всех вершин данного графа:

• Вершина $A$: 3 ребра (дуга к $B$, дуга к $H$, отрезок к $K$) — нечётная.
• Вершина $B$: 4 ребра (дуги к $A$ и $C$, отрезки к $K$ и $O$) — чётная.
• Вершина $C$: 2 ребра (дуги к $B$ и $D$) — чётная.
• Вершина $D$: 4 ребра (дуги к $C$ и $E$, отрезки к $O$ и $L$) — чётная.
• Вершина $E$: 3 ребра (дуга к $D$, дуга к $F$, отрезок к $L$) — нечётная.
• Вершина $F$: 4 ребра (дуги к $E$ и $G$, отрезки к $L$ и $O$) — чётная.
• Вершина $G$: 2 ребра (дуги к $F$ и $H$) — чётная.
• Вершина $H$: 4 ребра (дуги к $G$ и $A$, отрезки к $O$ и $K$) — чётная.
• Вершина $K$: 4 ребра (отрезки к $A, B, O, H$) — чётная.
• Вершина $L$: 4 ребра (отрезки к $E, D, O, F$) — чётная.
• Вершина $O$: 6 рёбер (отрезки к $B, D, L, F, H, K$) — чётная.

В данном графе ровно две вершины с нечётной степенью: $A$ и $E$. По условию Аня закончила обход в вершине $A$. Следовательно, начать обход она должна была в другой нечётной вершине — в вершине $E$.

Ответ: E