В графе, изображенном на рисунке, нужно провести одно ребро: AO, BM, AC или DK. В результате должен образоваться Эйлеров путь, то есть путь, соединяющий все вершины и проходящий через каждое ребро ровно по одному разу. Выберите ребро, которое нужно провести.

Для того, чтобы граф имел Эйлеров путь, необходимо и достаточно, чтобы в нем было не более двух вершин с нечетной степенью (количеством ребер, выходящих из вершины). Изначально в графе степени вершин следующие: - A: 3 - B: 3 - C: 2 - D: 2 - E: 2 - F: 2 - K: 3 - M: 2 - N: 2 - O: 2 Видим, что вершины A, B и K имеют нечетную степень. Для существования Эйлерова пути нам нужно, чтобы было только две вершины с нечетной степенью. 1) Добавление ребра AO: - A: 4 (четная) - O: 3 (нечетная) Теперь степени нечетные у B, K и O - не подходит. 2) Добавление ребра BM: - B: 4 (четная) - M: 3 (нечетная) Теперь степени нечетные у A, K и M - не подходит. 3) Добавление ребра AC: - A: 4 (четная) - C: 3 (нечетная) Теперь степени нечетные у B, K и C - не подходит. 4) Добавление ребра DK: - D: 3 (нечетная) - K: 4 (четная) Теперь степени нечетные у A, B и D - не подходит. Но так как нам нужно, чтобы число вершин нечетной степени было меньше 2, перепроверим все еще раз. Правильный способ рассуждения. Чтобы получить Эйлеров путь, необходимо, чтобы все вершины имели четную степень или только 2 вершины имели нечетную степень. В данном графе сейчас вершины A,B,K имеют нечетную степень. Если мы добавим ребро DK, то нечетными станут вершины A,B и D, что не подходит. Для построения Эйлерова пути добавление ребра DK не решит проблему. Однако мы забыли о том, что Эйлеров путь может начинаться и заканчиваться в разных вершинах, если у нас 2 вершины нечетной степени. Рассмотрим вариант с добавлением DK: - Степень вершины D станет 3 - Степень вершины K станет 4 Тогда у нас 3 вершины с нечетной степенью: A, B и D. Нужно еще раз проверить условие задачи: может быть существует какой-то подвох? Чтобы граф имел Эйлеров путь, необходимо и достаточно, чтобы не более двух вершин имели нечетную степень. Изначальный граф: A: 3 B: 3 K: 3 Добавление ребра DK: A: 3 B: 3 D: 3 K: 4 Действительно не подходит. Добавим ребро, соединяющее 2 нечетные вершины, например AK. В задаче нет такого варианта. Если добавить ребро AO: A: 4 O: 3 B: 3 K: 3 Тоже не подходит. По условиям задачи только один из вариантов верный. Перепроверим все еще раз: 1) AO 2) BM 3) AC 4) DK Ответ: 4) DK