Решение задачи 13.
В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно один раз.
Для существования такого цикла необходимо и достаточно наличия двух условий:
1. граф является связным;
2. степень любой вершины графа четна.
Первое условие очевидно. Второе следует из факта, что если такой цикл существует и заходит в некоторую вершину графа, то он должен и выйти из нее. Проверив эти условия (для проверки связности можно воспользоваться алгоритмом для задачи 11).
Предположим, что некоторый цикл А (не обязательно проходящий через все ребра графа) уже построен и из графа выброшены ребра цикла (их можно просто отметить как пройденные). Найдем вершину (пусть это вершина к), через которую этот цикл проходил, но которой инцидентны некоторые ребра (непройденные). Построим новый цикл В, который начинается в вершине к, по следующему правилу.
Находясь в текущей вершине цикла ( вначале это вершина к), находим непройденное еще ребро, инцидентное текущей вершине. Это ребро и определяет новую текущую вершину цикла, а ребро считается пройденным. Построение цикла В продолжается до тех пор, пока это возможно. Легко понять, что это будет цикл, так как степень любой вершины четна. Предположим, что построение цикла В завершено. Склеиваем теперь циклы А и В следующим образом. Находим в цикле А (последовательности вершин) вершину к и заменяем ее последовательностью вершин цикла В.
Такой процесс повторяется до тех пор, пока все ребра не будут пройдены. Описанный процесс можно начинать с пустого цикла А (пустой последовательности).
|
