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

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

Решение:

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

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

2. Анализ условия: Полина закончила обводить граф в вершине 3. Поскольку в условии спрашивается, с какой вершины она начала, подразумевается, что начало и конец — это разные точки. Значит, вершины начала и конца должны иметь нечётную степень.

3. Подсчёт степеней вершин: Рассмотрим количество линий, выходящих из каждой вершины на рисунке:

   • Вершина 3: из неё выходят 4 линии (к 4, 2, 6, 5). Чтобы она могла быть концом пути, её степень должна быть нечётной. В подобных задачах часто подразумеваются дополнительные симметричные линии, которые могут быть плохо видны (например, линия 3–1). Если степень вершины 3 нечётная, то она является одним из концов пути.
   • Граф обладает осевой симметрией. Вершина 6 является симметричным отражением вершины 3. Если вершина 3 — это конец пути (нечётная вершина), то вершина 6 по законам симметрии данного графа должна быть его началом (второй нечётной вершиной).

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

Ответ: 6