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

Решение:

Для того чтобы в графе существовал Эйлеров путь, в нём должно быть либо 0, либо 2 вершины с нечетной степенью. В данном графе степени вершин следующие:

• Степень вершины A: 3 (ребра AF, AD, AE)
• Степень вершины B: 2 (ребра BA, BC)
• Степень вершины C: 2 (ребра CB, CD)
• Степень вершины D: 3 (ребра DA, DC, DE)
• Степень вершины E: 2 (ребра EA, ED)
• Степень вершины F: 2 (ребра FA, FC)

Сейчас у нас две вершины с нечетной степенью: A и D. Чтобы образовался Эйлеров путь, нужно, чтобы все вершины имели четную степень (в случае Эйлерова цикла) или ровно две вершины имели нечетную степень. Так как у нас уже есть две вершины с нечетной степенью (A и D), мы можем провести ребро между ними. Тогда степени вершин станут:

• Степень вершины A: 3 + 1 = 4 (четная)
• Степень вершины B: 2 (четная)
• Степень вершины C: 2 (четная)
• Степень вершины D: 3 + 1 = 4 (четная)
• Степень вершины E: 2 (четная)
• Степень вершины F: 2 (четная)

В этом случае все вершины будут иметь четную степень, что означает существование Эйлерова цикла, который также является Эйлеровым путем.

Другой вариант: Если провести ребро между B и F, то степени вершин будут:

• A: 3 (нечетная)
• B: 2+1=3 (нечетная)
• C: 2 (четная)
• D: 3 (нечетная)
• E: 2 (четная)
• F: 2+1=3 (нечетная)

В этом случае будет 4 вершины с нечетной степенью, Эйлеров путь существовать не будет.

Если провести ребро между C и F, то степени вершин будут:

• A: 3 (нечетная)
• B: 2 (четная)
• C: 2+1=3 (нечетная)
• D: 3 (нечетная)
• E: 2 (четная)
• F: 2+1=3 (нечетная)

В этом случае будет 4 вершины с нечетной степенью, Эйлеров путь существовать не будет.

Таким образом, единственное ребро, которое можно провести, чтобы граф имел Эйлеров путь, это ребро между вершинами A и D.

Ответ: AD