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

Логика решения

Чтобы определить, в какой вершине Катя закончила обводить граф, нужно проследить ее путь, начиная с вершины С. Задача подразумевает, что Катя обвела весь граф, не отрывая карандаша и не проводя по одной линии дважды. Это означает, что она прошла по каждому ребру графа ровно один раз. Начать нужно с вершины С и пройти по всем рёбрам, придя в какую-то конечную вершину.

Давайте проследим возможный путь:

1. Начинаем в вершине С.
2. Идем в B (ребро CB).
3. Идем в A (ребро BA).
4. Идем в G (ребро AG).
5. Идем в F (ребро GF).
6. Идем в E (ребро FE).
7. Идем в D (ребро DE).
8. Идем в C (ребро CD).
9. Идем в L (ребро CL).
10. Идем в K (ребро LK).
11. Идем в H (ребро KH).
12. Идем в F (ребро HF). Здесь мы повторили ребро F-E, что запрещено.

Попробуем другой путь, чтобы обойти все вершины и рёбра:

1. Начинаем в вершине С.
2. Идем в B (ребро CB).
3. Идем в A (ребро BA).
4. Идем в G (ребро AG).
5. Идем в F (ребро GF).
6. Идем в H (ребро HF).
7. Идем в K (ребро HK).
8. Идем в L (ребро KL).
9. Идем в E (ребро LE).
10. Идем в D (ребро ED).
11. Идем в C (ребро DC).
12. Идем в L (ребро CL).
13. Идем в M (ребро LM).
14. Идем в N (ребро MN).
15. Идем в B (ребро NB). Здесь мы повторили ребро CB.

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

Давайте посчитаем степени вершин:

• A: 2 (BA, AG)
• B: 3 (CB, BA, NB) — нечётная
• C: 3 (CB, CD, CL) — нечётная
• D: 2 (CD, DE)
• E: 2 (DE, EF)
• F: 3 (EF, FG, FH) — нечётная
• G: 2 (AG, GF)
• H: 2 (FH, HK)
• K: 2 (KH, KL)
• L: 3 (CL, LK, LE) — нечётная
• M: 2 (LM, MN)
• N: 2 (MN, NB)

У нас есть 4 вершины с нечётной степенью: B (3), C (3), F (3), L (3). Это означает, что полный эйлеров путь (то есть проход по всем рёбрам ровно один раз) в данном графе невозможен, если бы он требовал только 0 или 2 вершины с нечётной степенью. Однако, в условии сказано, что Катя обвела граф, не отрывая карандаша и не проводя по одному ребру дважды. Это означает, что она совершила либо эйлеров цикл, либо эйлеров путь.

Если начать обход с вершины C (нечетная степень), то он должен закончиться в другой вершине с нечетной степенью. Возможные пары вершин для конца пути: (C, B), (C, F), (C, L). Поскольку Катя начала в C, она должна закончить в B, F или L.

Давайте проследим путь, который охватывает все рёбра, начиная с C и заканчивая в одной из вершин с нечетной степенью:

1. C → B → A → G → F → E → D → C (здесь мы прошли по внутреннему четырехугольнику CDEF и внешнему CBAGF, но не обошли K, L, H, M, N)

Попробуем другой путь:

1. C → L → K → H → F → G → A → B → N → M → L (здесь мы прошли по CL, LK, KH, HF, FG, GA, AB, BN, NM, ML, но ребро LE и CD остались не пройденными. Кроме того, вершина L была посещена дважды, а ребро CL было пройдено дважды.)

Так как в графе 4 вершины с нечетной степенью (B, C, F, L), то эйлерова пути (или цикла) не существует. Однако, если мы хотим пройти по всем ребрам, нам придется повторить хотя бы одно ребро. Задача гласит, что Катя