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

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

A B C D E F G

Решение

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

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

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

• Вершина $A$: 3 ребра ($AB, AF, AG$) — нечётная.
• Вершина $B$: 4 ребра ($BA, BC, BF, BG$) — чётная.
• Вершина $C$: 2 ребра ($CB, CD$) — чётная.
• Вершина $D$: 4 ребра ($DC, DF, DG, DE$) — чётная.
• Вершина $E$: 1 ребро ($ED$) — нечётная.
• Вершина $F$: 4 ребра ($FA, FB, FD, FG$) — чётная.
• Вершина $G$: 4 ребра ($GA, GB, GF, GD$) — чётная.

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

Ответ: A