В графе, изображённом на рисунке, нужно провести одно ребро: OK, AM, ML или DN. В результате должен образоваться Эйлеров путь, то есть путь, соединяющий все вершины и проходящий через каждое ребро ровно по одному разу. Выберите ребро, которое нужно провести.

Для решения этой задачи нам нужно понять, что такое Эйлеров путь и как его можно построить. Эйлеров путь – это путь в графе, который проходит через каждое ребро ровно один раз. Граф имеет Эйлеров путь, если в нём не более двух вершин с нечётной степенью (количество ребер, инцидентных вершине). В данном графе у нас есть следующие степени вершин: - A: 2 - L: 3 - B: 2 - O: 4 - N: 3 - K: 3 - D: 2 - M: 3 - C: 2 Сейчас у нас 4 вершины с нечётной степенью: L, N, K, M. Чтобы получить Эйлеров путь, нам нужно, чтобы их было не больше двух. Для этого нужно добавить ребро между двумя из этих вершин. Проверим предложенные варианты: 1) OK: Если добавим ребро OK, степени вершин станут: - O: 5 - K: 4 Теперь нечётные вершины: L, N, K, M, O. Слишком много. 2) AM: Если добавим ребро AM, степени вершин станут: - A: 3 - M: 4 Теперь нечётные вершины: L, N, K, A. Слишком много. 3) ML: Если добавим ребро ML, степени вершин станут: - M: 4 - L: 4 Теперь нечётные вершины: N, K. Всего две, значит, это подходит. 4) DN: Если добавим ребро DN, степени вершин станут: - D: 3 - N: 4 Теперь нечётные вершины: L, K, M, D. Слишком много. Таким образом, добавление ребра ML сделает граф пригодным для Эйлерова пути, так как в графе останется только две вершины с нечётной степенью (N и K). Ответ: 3) ML