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

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

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

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

ДЕЛО 1 :

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

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

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

СЛУЧАЙ 2:

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

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

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

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

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

e.g.

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), БК -> АБ (стоимость 1) }

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

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

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