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

Question

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

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

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

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

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

Answer 1

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

Известно, что граф содержитпуть Эйлера тогда и только тогда, когда он СОЕДИНЕН и имеет все вершины (кроме 2) ДАЖЕ СТЕПЕНИ.Это можно сделать, выполнив следующие действия:

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

CASE 1:

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

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

  CASE 2:

  • Подграф, состоящий только из нужных ребер, содержит более одного компонента.Чтобы обеспечить связь, выполните следующие действия: - Возьмите компонент с минимальным количеством вершин.Сделайте BFS из каждой вершины и выберите путь минимальной длины, который соединяет этот компонент с ЛЮБОМ ДРУГИМ компонентом.

  • Повторяйте эту процедуру, пока все компоненты не объединятся в один компонент.Теперь для четности выполните процедуру, описанную ранее для СЛУЧАЯ 1.

Answer 2

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

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

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

Answer 3

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

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

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

, например

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

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