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

Для решения этих задач важно вспомнить правило: если у графа есть вершины с нечетной степенью (в которых сходится нечетное число ребер), то путь можно начать в одной из нечетных вершин, а закончить в другой. Если все вершины четные, путь можно начать в любой вершине и закончить в ней же. ### 11.1 Посчитаем степени вершин: - E: 3 ребра (нечетная) - B: 4 ребра (четная) - C: 4 ребра (четная) - F: 4 ребра (четная) - O: 4 ребра (четная) - D: 1 ребро (нечетная) У графа две нечетные вершины: E и D. Так как Света начала в E, она обязана закончить в другой нечетной вершине — D. **Ответ: D** ### 11.2 Посчитаем степени вершин: - A: 4 ребра (четная) - B: 4 ребра (четная) - C: 4 ребра (четная) - D: 2 ребра (четная) - E: 4 ребра (четная) - F: 4 ребра (четная) - G: 4 ребра (четная) - H: 4 ребра (четная) Все вершины имеют четную степень. В таком случае обход можно начать в любой вершине, и закончить придется в той же самой. Так как Люда закончила в G, значит, она начинала в G. **Ответ: G** ### 11.3 Посчитаем степени вершин: - B: 2 ребра (четная) - A: 4 ребра (четная) - F: 2 ребра (четная) - E: 4 ребра (четная) - C: 4 ребра (четная) - D: 2 ребра (четная) - O: 4 ребра (четная) Все вершины имеют четную степень. Это значит, что существует Эйлеров цикл: можно начать с любой вершины и вернуться в нее же. Ваня может начать с любой из них. **Ответ: С любой вершины** ### 11.4 Посчитаем степени вершин текущего графа: - A: 3 (A-D, A-F, A-O) — нечетная - D: 2 (A-D, D-B) — четная - B: 3 (B-D, B-E, B-F) — нечетная - E: 2 (B-E, E-C) — четная - C: 3 (C-E, C-F, C-O) — нечетная - F: 3 (F-A, F-C, F-O) — нечетная - O: 3 (O-A, O-C, O-F) — нечетная Итого 5 нечетных вершин (A, B, C, F, O). Чтобы существовал Эйлеров путь, должно остаться ровно две нечетные вершины (начало и конец) или ноль. Проверим варианты добавления ребра: - Если добавить ребро AB: степени станут 4, 3, 4, 2, 3, 3, 3 (не подходит). - Если добавить ребро OE: E станет 3, O станет 4. Останется 4 нечетных вершины (не подходит). - Если добавить ребро DE: D станет 3, E станет 3. Останется 7 нечетных (не подходит). - Если добавить ребро DF: D станет 3, F станет 4. Останется 4 нечетных (не подходит). *Примечание:* Вероятно, в условии опечатка или требуется соединить вершины так, чтобы "убрать" нечетность. Если мы соединим две нечетные вершины, их степени станут четными. В задаче нужно добиться того, чтобы осталось 2 нечетные вершины. Нужно соединить пару нечетных вершин. Единственный логичный вариант для Эйлерова пути здесь — попробовать соединить вершины так, чтобы четность изменилась нужным образом. Если соединить A и B, их степени из 3 станут 4. Останутся нечетными C, F, O (три вершины — мало). Похоже, здесь опечатка в списке вариантов, но из предложенных вариантов корректным для уменьшения числа нечетных вершин является соединение любых двух нечетных. Лучший выбор здесь — **AB** (или OE, если бы это давало нужный результат). **Ответ: AB**