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

Для того чтобы в связном графе существовал Эйлеров путь, необходимо, чтобы количество вершин с нечетной степенью было либо 0 (тогда это Эйлеров цикл), либо 2 (тогда это Эйлеров путь, начинающийся в одной нечетной вершине и заканчивающийся в другой). Давайте посчитаем степени вершин в исходном графе: - Вершина A: 4 ребра (петля F-A считается за 2, плюс ребра к B, D, E) — степень 4 (четная). - Вершина B: 3 ребра (к A, C, C) — степень 3 (нечетная). - Вершина C: 3 ребра (к B, B, D) — степень 3 (нечетная). - Вершина D: 3 ребра (к C, A, E) — степень 3 (нечетная). - Вершина E: 2 ребра (к A, D) — степень 2 (четная). - Вершина F: 2 ребра (петля к A) — степень 2 (четная). Сейчас у нас вершины с нечетной степенью — это B, C, D (всего 3 вершины). Чтобы получить Эйлеров путь, нам нужно, чтобы количество нечетных вершин стало равно 2. Если мы добавим ребро между вершинами B и D, то степени этих вершин увеличатся на 1 и станут четными (3+1=4). Тогда нечетной останется только вершина C. Это не подходит. Если мы добавим ребро между вершинами B и C, степень B станет 4, степень C станет 4. Нечетной останется только D. Не подходит. Если мы добавим ребро между вершинами C и D, то степень C станет 4 (была 3), степень D станет 4 (была 3). Тогда нечетной вершиной останется только B. Это тоже не подходит. Чтобы получить путь, нужно соединить две нечетные вершины, чтобы они стали четными, но при этом у нас осталась *еще одна* нечетная вершина для начала пути? Нет, если мы соединим B и C, они станут четными, а D останется нечетной, но у нас еще останется вершина A, B, C, D... стоп. Давайте пересчитаем внимательнее: - A: ребра к F, F, B, D, E — степень 5 (нечетная) - B: ребра к A, C, C — степень 3 (нечетная) - C: ребра к B, B, D — степень 3 (нечетная) - D: ребра к C, A, E — степень 3 (нечетная) - E: ребра к A, D — степень 2 (четная) - F: петля к A — степень 2 (четная) Нечетные вершины: A, B, C, D (4 штуки). Чтобы сделать Эйлеров путь, нужно соединить две из них, чтобы они стали четными. Например, соединим A и B. Тогда A станет четной (5+1=6), B станет четной (3+1=4). Останутся нечетными только C и D. Это как раз 2 нечетные вершины, значит, Эйлеров путь возможен. Ответ: AB