Алгоритм обхода края графа, некоторые необходимые края, некоторые необязательные

Question

У меня есть неориентированный граф со всеми вершинами четной степени. На этом графике есть набор ребер, которые должны быть покрыты ровно один раз, и множество ребер, которые не должны быть покрыты вообще, если это абсолютно необходимо. Мне нужно найти набор из одного или нескольких путей через граф, так что все требуемые ребра будут покрыты ровно один раз, а количество пересеченных нежелательных кромок минимизировано. Никакой требуемый край не может пересекаться более чем одним путем, но нежелательные края могут пересекаться любым количеством путей. Это не совсем эйлеровский путь, потому что есть дополнительные края.

Длина каждого отдельного пути ограничена максимальным количеством требуемых краев, которые он может покрыть, хотя путь может охватывать любое количество нежелательных краев.

Начальные и конечные пункты не обязательно должны быть одинаковыми, но существует множество возможных исходных точек.

Некоторые из нежелательных ребер совпадают с требуемыми ребрами - то есть пара вершин может иметь как обязательный край, так и нежелательный край между ними (хотя никогда не будет более одного края каждого типа между заданная пара вершин).

Для чего нужен хороший алгоритм? По сути, я ищу алгоритм, который может найти путь, который пересекает требуемые края ровно один раз и позволяет избежать нежелательных краев, когда это возможно (но может пересекать их более одного раза, если необходимо). Я могу опираться на это, чтобы сделать все остальное.

Answer 1

Вы ищете подграф в исходном графе, так что он содержит все необходимые ребра с минимальными нежелательными краями, такими как эйлеровы дорожка.

Известно, что граф содержит эйлеровский путь тогда и только тогда, когда он ПОДКЛЮЧЕН и имеет все вершины (кроме 2) значения EVEN DEGREE. Это можно сделать, выполнив следующие действия:

• Начните с прямого включения всех желаемых ребер в итоговый подграф. Теперь у вас есть график с одним или несколькими подключенными компонентами.

СЛУЧАЙ 1:

• Если число компонентов в этом подграфа один (то есть, все ребра соединены друг с другом), то только для того, чтобы все вершины (кроме 2) имеют четную степень. Поскольку ваш исходный граф имеет все вершины четной степени, это можно сделать, но мы также хотим позаботиться о том, чтобы количество ребер, которые мы добавляем для достижения этого, минимально (поскольку для добавления осталось только нежелательные края).

• Один хороший эвристический способ сделать это, начать с каждой из вершин нечетной степени и выполнить BFS (поиск по ширине) до тех пор, пока вы не достигнете другой вершины с нечетной степенью. Сделайте это для всех вершин с нечетной степенью, выберите две вершины, которые берут максимальный нежелательный путь между ними для достижения этого и удаляют этот путь. Теперь граф будет иметь эйлеров путь

(Одна вещь, чтобы отметить, что такое спаривание нечетных вершин всегда возможно, так как ни граф не может иметь нечетное число вершин нечетной степени)

CASE 2:

• Подграф, состоящий из только желаемых ребер, имеет более одного компонента. Чтобы обеспечить подключение, выполните следующие действия: возьмите компонент с минимальным количеством вершин. Сделайте BFS из каждой из вершин и выберите путь минимальной длины, который соединяет этот компонент с любым другим компонентом.

• Повторяйте эту процедуру до тех пор, пока все компоненты не сольются, чтобы сформировать один компонент. Теперь даже Несс следовать процедуре, описанной выше для случая 1.

Answer 2

Я думаю, что это можно свести к Проблема с продавцом. Создайте преобразованный граф, где узлы представляют собой обязательные ребра, а вес границ ребер представляет количество необязательных ребер, которые необходимо пройти, чтобы перейти от одного обязательного края к другому.

Теперь проблема заключается в том, чтобы найти кратчайший путь в этом преобразованном графе, который проходит через все узлы (или обязательные ребра). Это TSP, который NP-жесткий.

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

например.

A===C 
|/
|/   (edges A<->B and B<->C are compulsory, A<=>C is optional) 
|/ 
B 

Преобразованный граф:
Узлы = {АВ, ВА, БК, СВ}
фронтам = {АВ -> БК (стоимость 0), ВА -> СВ (стоимость 1), CB -> Б.А. (стоимость 0), BC -> AB (стоимость 1)}

Answer 3

Это NP-трудной: экземпляр гамильтоновой задачи пути может быть преобразован в экземпляр вашей проблемы. Поэтому, если вы знаете, как решить свою проблему, вы знаете, как решить проблему пути Гамильтона.

Чтобы преобразовать, возьмите ориентированный граф и удвоьте каждую вершину, скажем, в красную и синюю вершины. Для каждой бывшей вершины сделайте все входящие ребра переходящими в красную вершину, и все исходящие ребра выйдут из голубой вершины. Сделайте один новый край от красного до синей вершины. Очевидно, что если вы можете решить проблему цикла Гамильтона для этого графа, вы можете сделать это для исходного графика.

Теперь обозначьте все новые ребра обязательными, все старые края по желанию. Отметьте одну красную вершину как возможную точку входа. Если есть решение вашей проблемы, то она состоит из одного пути, который является гамильтоновым путем для исходного графика.