zad 6 koło PAA z 2012 roku

Zadanie 6 (20pkt)
Wiadomo że problem komiwojażera jest NP-trudny. Opisz rozumowanie pozwalające
ustalić, czy pozostanie on NP-trudny czy wielomianowy, gdy w grafie nwierzchołkowym:
a) wszystkie wagi krawędzi będą parzyste
b) wszystkie wagi krawędzi będą nieparzyste
c) wszystkie wagi krawędzi będą identyczne
d) wszystkie wagi krawędzi należą do zbioru {1,n} i z każdego wierzchołka wychodzą
co najwyżej 2 krawędzie jednostkowe
e) wszystkie wagi krawędzi należą do zbioru {1,n} i z każdego wierzchołka wychodzi
co najmniej n-2 krawędzi jednostkowych

ale chodzi o wersje optymalizacyjną?
bo decyzyjna należy do npc, choć npc należy do nph więc nie wiem. herp.

a) NPH bo wystarczyłoby przemnożyć wagi krawędzi przez 2 żeby problem stał się P
b) NPH bo wystarczyłoby każdą wagę krawędzi zamienić na liczbę nieparzystą (2w + 1) żeby problem stał się P
c) NPH bo problem cyklu hamiltona dla grafu pełnego który można
zredukować wielomianowo w prosty sposób do tego przypadku również jest NPH.
d) em.. zakładam, że to nie digraf więc po prostu stopień wierzchołka <= 2?
P. bo taki graf jest albo ścieżką albo cyklem. Jeżeli jest cyklem to wynikiem jest suma wag wszystkich krawędzi.
Jeżeli nie jest cyklem to nie ma drogi komiwojażera dla danego grafu.
e)
można zredukować problem znajdowania cyklu hamiltona do tego przypadku.
Z grafu dla problemu cyklu hamiltona robimy graf pełny. Jeżeli krawedź była, dostaje wage 1.
Jeżeli jej nie było dostaje wagę n. Gdyby to uszczególnienie problemu komiwojażera było wielomianowe
to hamiltona też możnaby rozwiązać w czasie wielomianowym. I dzieki temu decyzyjnego hamiltona
też dałoby się rozwiązać w czasie wielomianowym, co znaczyloby, że P=NP, czego jeszcze nikt nie udowodnił.