В задаче требуется разбить ребра графа на две группы, каждая из которых образует путь в графе. Ясно, что каждый путь содержится в одной компоненте связности. Поэтому если в данном графе больше двух компонент связности, то задача не имеет решения. То же самое можно сказать про граф, в котором более четырех вершин нечетной степени. Действительно, каждая вершина в пути имеет четную степень, за исключением первой и последней вершины. Поэтому объединение двух путей не может содержать больше четырех нечетных вершин.
Теперь рассмотрим случаи:
1. Одна компонента связности, нет вершин нечетной степени. Тогда имеем эйлеров цикл, который можно разбить на два пути.
2. Одна компонента связности, две нечетные вершины. То же самое, только с эйлеровым путем вместо эйлерова цикла. Есть один хитрый случай: граф с одним ребром, который не может быть разбит на два непустых пути.
3. Одна компонента связности, четыре нечетные вершины. Самый интересный случай. Соединим две вершины нечетной степени фиктивным ребром. Получим граф, содержащий эйлеров путь. Найдем эйлеров путь и удалим фиктивное ребро - получим два пути.
4. Две компоненты связности, каждая имеет ноль или две нечетные вершины. Два эйлеровых пути/цикла.
5. Две компоненты связности, четыре нечетные вершины в одной и ни одной нечетной вершины в другой. Нет решения.
Комментарии (0)
