В графе, изображённом на рисунке, нужно удалить одно ребро так, чтобы в результате образовался Эйлеров путь (путь, проходящий через каждое ребро ровно по одному разу). Запишите ребро, которое нужно удалить. Для записи используйте заглавные латинские буквы.

Question

Вопрос:

В графе, изображённом на рисунке, нужно удалить одно ребро так, чтобы в результате образовался Эйлеров путь (путь, проходящий через каждое ребро ровно по одному разу). Запишите ребро, которое нужно удалить. Для записи используйте заглавные латинские буквы.

Ответ:

Accepted Answer

Краткое пояснение: Эйлеров путь существует, когда в графе не более двух вершин с нечётной степенью. Сейчас нечётные вершины: D, C, A и B. Чтобы их осталось только две, нужно удалить ребро, соединяющее две из этих вершин.

Решение:

Удалим ребро AD. Тогда степени вершин станут:

A: 2

B: 3

C: 3

D: 2

E: 2

F: 2

G: 2

H: 2

Теперь только две вершины (B и C) имеют нечётную степень, что позволяет построить Эйлеров путь.

Ответ: AD