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

Для того чтобы в графе существовал Эйлеров путь, необходимо, чтобы в графе было не более двух вершин нечетной степени. Подсчитаем степени вершин графа: - A: 2 - B: 2 - C: 2 - D: 2 - E: 2 - F: 2 Все вершины имеют четную степень. Чтобы образовался Эйлеров путь, нужно добавить ребро, которое создаст две вершины нечетной степени. - Если добавить AE, то степени вершин A и E станут равны 3. - Если добавить BD, то степени вершин B и D станут равны 3. - Если добавить BE, то степени вершин B и E станут равны 3. - Если добавить DF, то степени вершин D и F станут равны 3. В любом случае после добавления одного из предложенных ребер в графе будет ровно две вершины нечетной степени, следовательно, Эйлеров путь будет существовать. Рассмотрим вариант с ребром BE: После добавления ребра BE, степени вершин B и E станут равны 3. Эйлеров путь должен соединять все вершины. Проверим, можно ли построить Эйлеров путь: A - B - C - D - E - F - A. Добавляем BE. A - B - E - D - C - B. Ответ: BE (3)