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

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