Алгоритъм за обхождане на ръба на графиката, някои ръбове са задължителни, някои по избор

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

Известно е, че графът съдържа Ойлеров път тогава и само ако е СВЪРЗАН и има всички върхове (с изключение на 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), BC -> AB (цена 1) }

Това е NP-трудно: екземпляр на проблема с хамилтоновия път може да се трансформира в екземпляр на вашия проблем. Следователно, ако знаете как да решите проблема си, знаете как да решите проблема с хамилтоновия път.

За да трансформирате, вземете насочен граф и удвоете всеки връх, да речем, в червен и син връх. За всеки бивш връх накарайте всички входящи ръбове да отиват към червения връх, а всички изходящи ръбове да излизат от синия връх. Направете един нов ръб от червения до синия връх. Очевидно, ако можете да решите проблема с Хамилтоновия цикъл за тази графика, можете да го направите и за оригиналната графика.

Сега маркирайте всички нови ръбове като задължителни, всички стари ръбове като незадължителни. Маркирайте единичен червен връх като възможна входна точка. Ако има решение на вашия проблем, тогава то се състои от един път, който е хамилтонов път за оригиналната графика.