Задача китайского почтальона
Суть задачи такова: имеется связный неориентированнй граф, ребрам которого приписаны веса. В графе имеется не более двух вершин с нечетной степенью (то есть вершина связана с нечетным кол-вом других вершин). Требуется обойти все ребра графа, и чтобы этот путь был минимален по стоимости. Путь должен начинаться и заканчиваться в одной и той же вершине, начинать можно с любой вершины.
Если в графе нет вершин нечетной степени, то алгоритм сводится к поиску эйлерова цикла, а если таких вершин 2, то существует только эйлеров путь. В первом случае задача сводится к нахождению эйлерова цикла.
А теперь, собственно, вопрос касательно второго случая (нечетных вершин 2): будет ли решение оптимальным, если сначала найти эйлеров путь из одной вершины нечетной степени в другую, а потом по алгоритму Дейкстры найти кратчайший путь обратно? И если нет, то как использовать тот факт, что вершин нечетной степени не больше двух?
Если в графе нет вершин нечетной степени, то алгоритм сводится к поиску эйлерова цикла, а если таких вершин 2, то существует только эйлеров путь. В первом случае задача сводится к нахождению эйлерова цикла.
А теперь, собственно, вопрос касательно второго случая (нечетных вершин 2): будет ли решение оптимальным, если сначала найти эйлеров путь из одной вершины нечетной степени в другую, а потом по алгоритму Дейкстры найти кратчайший путь обратно? И если нет, то как использовать тот факт, что вершин нечетной степени не больше двух?