Niech będzie wykresem niekierowanym. Rozkładem V na podzbiory rozłączne V i nazywa się Hamilton rozkładu z G jeśli subgraph wywołanych przez każdy zestaw V i jest albo wykres Hamiltona lub składa się z jednej krawędzi z | V i | = 2 .
Przykład : Pełny dwudzielny wykres ma rozkład Hamiltona wtedy i tylko wtedy, gdy m = n .
Szukam algorytmu, który decyduje, czy dany wykres ma rozkład Hamiltona. Czy problem decyzyjny NP jest kompletny? Jeśli nie, to jak możemy znaleźć taki rozkład?
Uwaga : W literaturze często rozkładowi Hamilton oznacza rozkład krawędzie z G taki sposób, że są indukowane subgraphs Hamiltona. Natomiast interesuje mnie rozkład wierzchołków.