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

Для того чтобы нарисовать граф, не отрывая карандаша и не проводя по одному ребру дважды (нарисовать эйлеров путь), нужно посчитать степени вершин (количество рёбер, выходящих из каждой вершины). Эйлеров путь возможен, если количество вершин с нечётной степенью равно 0 или 2. В последнем случае путь начинается в одной вершине с нечётной степенью и заканчивается в другой. Посчитаем степени вершин: - A: 3 ребра (AB, AG, AI) — нечётная - B: 5 рёбер (BC, BD, BA, BG, BF) — нечётная - C: 2 ребра (CB, CD) — чётная - D: 4 ребра (DC, DB, DE, DF) — чётная - E: 2 ребра (ED, EF) — чётная - F: 4 ребра (FE, FD, FG, FI) — чётная - G: 4 ребра (GB, GD, GF, GA, GI) — стоп, пересчитаем внимательно: - G соединена с B, D, F, A, I. Посмотрим на граф: - G соединена с: B, D, F, A, I. Итого 5 ребер — нечётная - I: 3 ребра (IA, IG, IF) — нечётная Давайте пересчитаем степени вершин по рисунку внимательно: - A: 3 (AB, AG, AI) — нечётная - B: 5 (BC, BA, BD, BG, BF) — нечётная - C: 2 (CB, CD) — чётная - D: 4 (DC, DB, DE, DF) — чётная - E: 2 (ED, EF) — чётная - F: 4 (FE, FD, FG, FI) — чётная - G: 3 (GB, GF, GI) — нечётная - I: 3 (IA, IG, IF) — нечётная Ой, в графе 4 нечётных вершины (A, B, G, I). Граф нельзя нарисовать одним росчерком (Эйлеров путь невозможен). Перепроверим граф на изображении еще раз: - C: 2 (CB, CD) - B: 4 (BC, BA, BD, BG) - D: 4 (DC, DB, DE, DF) - A: 3 (AB, AG, AI) - G: 4 (GB, GD, GF, GI) - F: 4 (FE, FD, FG, FI) - E: 2 (ED, EF) - I: 3 (IA, IG, IF) Теперь нечётные вершины только A и I. Значит, путь должен начинаться в одной из них и заканчиваться в другой. Так как сказано, что он закончил в вершине I, значит начал он в вершине A. **Ответ: A**