To pytanie powstaje z czystej ciekawości (pojawiło się podczas myślenia o odtasowaniu łańcucha , ale nie jestem pewien, czy jest rzeczywiście powiązane), więc mam nadzieję, że jest odpowiednie.
Istnieje wiele produktów graficznych i interesuje mnie którykolwiek z nich. Jaka jest złożoność ustalenia, czy wykres jest izomorficzny w stosunku do nietrywialnego produktu? (Z pewnością dla iloczynu kartezjańskiego K = K ◻ 1, gdzie 1 jest wykresem z jednym wierzchołkiem.)
Przejrzałem strony „wykres czynników” i „rozkład współczynników wykresów” na Wikipedii, ale żadne z nich nie wydaje się powiązane. Czy ten problem jest znany pod inną nazwą?
Kilka produktów grafowych można rozpoznać w czasie wielomianowym. Jak zwykle produkt kartezjański jest najłatwiejszy, a przypadek kartezjański jest również podstawą algorytmów dla kilku innych produktów. Rozpoznanie produktu leksykograficznego (składu) jest równoważne z izomorfizmem grafowym.
Bardziej szczegółowo:
Niech będzie klasą skończonych prostych grafów, a Γ 0 będzie klasą skończonych prostych grafów, które mogą mieć pętle własne. (Wyraźnie Γ ⊂ Γ 0. )Γ Γ0 Γ⊂Γ0
Decyzję, czy podłączony wykres wejściowy ma czynniki w Γ 0, można podjąć w czasie wielomianowym dla produktów kartezjańskich i silnych, a także dla produktu bezpośredniego, gdy G nie jest dwustronna. Decyzja o tym, czy G ma czynniki w Γ, jest w czasie wielomianowym dla produktu kartezjańskiego, ale jest mało prawdopodobne, że będzie w czasie wielomianowym dla produktu leksykograficznego. Nie znam statusu decydowania, czy G ma czynniki Γ dla bezpośrednich i mocnych produktów.G Γ0 G G Γ G Γ
Odpowiednie wyniki Imricha i Klavžara:
W przypadku produktu leksykograficznego:
Tak więc podjęcie decyzji, czy wykres jest liczbą pierwszą w odniesieniu do produktu leksykograficznego, jest równoważne z izomorfizmem graficznym w odniesieniu do redukcji Turinga.
Przypadek bezpośredniego i silnego produktu z czynnikami bez pętli wydaje się być nieobecny w referencjach, na które patrzyłem. Byłbym wdzięczny za wszelkie wskazówki do artykułów omawiających tę sprawę lub wskazówkę, dlaczego jest to nieciekawe.
źródło
Istnieje algorytm czasu liniowego do określania czynników pierwotnych połączonych wykresów w odniesieniu do iloczynu kartezjańskiego. Zobacz artykuł Imricha i Peterina.
źródło