11 В графе, изображённом на рисунке, нужно провести одно ребро: АО, ВМ, АС или DK. В результате должен образо- ваться Эйлеров путь, то есть путь, соединяющий все вер- шины и проходящий через каждое ребро ровно по одному разу. Выберите ребро, которое нужно провести. 1) AO 2) BM 3) AC 4) DK

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

Подсчитаем степени вершин в исходном графе:

• A: 3
• B: 3
• C: 2
• D: 2
• E: 2
• F: 2
• K: 4
• M: 2
• N: 2
• O: 3

Вершины A, B и O имеют нечетную степень. Чтобы получить Эйлеров путь, нужно добавить одно ребро так, чтобы остались только две вершины с нечетной степенью. Возможные варианты:

• Если добавить AO: A и O станут четными, а B останется нечетной. Не подходит.
• Если добавить BM: B и M станут четными, а A и O останутся нечетными. Число вершин с нечетной степенью становится равным 2. Подходит.
• Если добавить AC: A станет четной, C станет нечетной, O и B остаются нечетными. Число вершин с нечетной степенью не становится равным 2. Не подходит.
• Если добавить DK: D станет нечетной, K станет нечетной, O и B остаются нечетными. Число вершин с нечетной степенью не становится равным 2. Не подходит.

Таким образом, добавление ребра BM приводит к тому, что в графе будет только две вершины (A и O) с нечетной степенью, что позволит создать Эйлеров путь.

Ответ: 2) BM