Czy ktoś może wyjaśnić, jak znaleźć liczbę cykli Hamiltona na kompletnym nieukierunkowanym wykresie?Jak mogę znaleźć liczbę cykli Hamiltonian w kompletnym nieukierunkowanym grafie?
że formuła to (n-1)!/2, ale kiedy obliczyłem używając tej formuły, K3 ma tylko jeden cykl i K4 ma 5. Czy moje obliczenia były nieprawidłowe?
Po ukończeniu wykresu, każda permutacja zaczynająca się od ustalonego wierzchołka daje (prawie) unikalny cykl (ostatni wierzchołek w permutacji będzie miał krawędź z powrotem do pierwszego, ustalonego wierzchołka. Z wyjątkiem jednej rzeczy: jeśli odwiedzaj wierzchołki w cyklu w odwrotnej kolejności, to jest naprawdę ten sam cykl (z tego powodu liczba ta jest równa połowie permutacji (n-1) wierzchołków)
np. dla wierzchołków 1,2 , 3, ustalić "1" i masz:
ale 123 odwrócone (321) jest obrót (132), ponieważ 32 jest 23 odwrócone.
Istnieją (n-1)! permutacje nie-ustalonych wierzchołków, a połowa z nich jest odwrotnością drugiego, tak więc są one (n-1)!/2 odrębnymi cyklami Hamiltona na pełnym wykresie n wierzchołków.
W odpowiedzi na Twój komentarz Google Code Jam, zobacz this SO question
Zrobiłeś błąd podczas obliczyli łączną liczbę cykli.
Cykl hamiltonski musi zawierać wszystkie krawędzie. k4 ma tylko 3 takie cykle iw sumie ma 5 cykli, więc wzór jest poprawny.
Cykl Hamiltona odwiedzi wszystkie * wierzchołki * raz. Nie musi zawierać wszystkich krawędzi. – davitenio
Myślę, że gdy mamy cykl Hamiltona, ponieważ każdy wierzchołek leży w cyklu Hamiltona, jeśli rozważymy jeden wierzchołek jako cykl początkowy i końcowy. powinniśmy użyć 2 krawędzi tego wierzchołka. Tak więc mamy (n-1) (n-2)/2 cykl Hamiltona, ponieważ powinniśmy wybrać 2 krawędzie krawędzi n-1, które są połączone z tym wierzchołkiem.
ładne wyjaśnienie – avd
Zadałem to pytanie w odniesieniu do ubiegłorocznego Kodu Pytanie Kabinowe. Ale nadal nie jestem w stanie wymyślić algorytmu. Czy możesz wyjaśnić to pytanie o zakorkowanie kodu http://code.google.com/codejam/contest/dashboard?c=32004#s=p2 – avd
Mogę wygenerować wszystkie permutacje 2 ... n, gdzie 2 występuje w pierwszej połowie, i przeskocz nad tymi, które dają jedną z zabronionych krawędzi, tj. jeśli twoje permutacje to 4235 (co oznacza cykl 142351 ...), pomiń go, jeśli 14 42 23 35 lub 51 są zabronione. Możesz to zrobić, generując permutacje, np. gdyby 14 było zabronione, to byś zatrzymał się na "4 ..." –