Czy następujący problem NP-jest kompletny? (Zakładam, że tak).
Wprowadź: niekierowany wykres, na którym zbiór zboczy może zostać rozłożony na dwa proste cykle rozłączne od krawędzi ( nie są one częścią danych wejściowych).
Pytanie: Czy istnieje prosty cykl w o długości większej niż ?k
Oczywiście problem dotyczy NP, a maksymalny stopień w wynosi , ale to nie wydaje się pomocne.≤ 4
graph-theory
np-complete
decision-problem
Wymienianie kolejno
źródło
źródło
Odpowiedzi:
Próba redukcji ....
Redukcja ze ścieżki hamiltonowskiej na wykresie z maksymalnym stopniem 3, którym jest NPC [G&J]G = ( V, E)
Na wynikowym wykresie wszystkie żółte węzły można pokonywać prostą ścieżką tylko na dwa sposoby pokazane na rysunku E i rysunku F, które odpowiadają dwóm prawidłowym przemianom pierwotnego węzła ; nieformalnie, jeśli używana jest krawędź w kierunku dodatkowego „łączącego” fioletowego węzła, żółtych węzłów nie można przejść.b ∈ V k3 tys b ∈ V k
Wybór wystarczająco dużego, wykres wynikowy ma prostą ścieżkę o długości większej niż wtedy i tylko wtedy, gdy oryginalny wykres ma ścieżkę hamiltonowską (o długości )G ′ 3 k ( | V | - 1 ) G | V | - 1k ≫ | V.| G′ 3k(|V|−1) G |V|−1
Większy obraz można pobrać tutaj
źródło
Zainspirowany odpowiedzią Vora, chcę dać prostszą.
Rozpocznij od problemu cyklu Hamiltona dla problemu grafów siatkowych, który został udowodniony przez Itai.
Łatwo można zauważyć, że zestaw krawędzi wykresu siatki można podzielić na 2 rozłączne podzestawy: poziomy i pionowy.
Tak więc teraz musimy połączyć wszystkie poziome w jeden prosty cykl, a wszystkie w pionie w inny prosty cykl.
Jest to bardzo łatwe zadanie: w przypadku pionowych przeciągnij od lewej do prawej, po prostu połącz wszelkie pionowe szczeliny, a następnie połącz kolejne pionowe linie o współrzędnej x, a następnie połącz najniższy skrajny lewy wierzchołek z najwyższym skrajnym prawym wierzchołkiem. Zrób podobnie dla poziomych krawędzi.
Zauważ, że otrzymany wykres jest nadal prosty, bezkierunkowy i spełnia wymagania. Jest to proste, ponieważ na ostatnich etapach fazy pionowej i fazy poziomej mamy do czynienia z dwiema różnymi parami wierzchołków.
źródło