Grafy-cykl Hamiltona

[miodzio1988]

Dla tych co lubią teorie grafów mam zagadke. Oto ona:
Ile cykli Hamiltona ma graf \(\displaystyle{ K_{n,n}}\)dla n \(\displaystyle{ \geqslant}\)2 ?
Jakoś trzeba rozbudzić nasze forum Zadanie nie jest trudne. Za tydzień podam rozwiązanie(chyba, że ktoś wcześniej rozwiąże to zadanie )
Miłego myślenia życzę

[Szemek]

Moim zdaniem liczba unikalnych cykli Hamiltona w grafie: \(\displaystyle{ K_{n,n}}\) wynosi: \(\displaystyle{ \frac{n!(n-1)!}{2}}\)

Podzielmy zbiór wierzchołków na dwie klasy:
\(\displaystyle{ X = \{1,2,3,...,n\} \\
Y=\{1',2',3',...,n'\}}\)
Wybieram wierzchołek z którego będę zawsze startował i w nim kończył cykl Hamiltona.
Niech będzie to wierzchołek \(\displaystyle{ 1}\) z klasy \(\displaystyle{ X}\)
Cykle wyglądają następująco:
\(\displaystyle{ 1 \to \underbrace{(y_1^\prime \in Y)}_{n} \to \underbrace{(x_2 \in X)}_{n-1} \to \underbrace{(y_2^\prime \in Y)}_{n-1} \to ... \to \underbrace{(x_n \in X)}_{1} \to \underbrace{(y_n^\prime \in Y)}_{1} \to 1}\)
gdzie każdy wierzchołek z danej klasy pojawia się dokładnie raz i zostają użyte wszystkie wierzchołki.
Liczba wszystkich cykli:
\(\displaystyle{ n(n-1)(n-1)(n-2)(n-2)\cdot ... \cdot 2 \cdot 2 \cdot 1 \cdot 1 = n!(n-1)!}\), czyli liczba permutacji \(\displaystyle{ (n-1)}\) wierzchołków z klasy \(\displaystyle{ X}\) razy liczba permutacji \(\displaystyle{ n}\) wierzchołków z klasy \(\displaystyle{ Y}\)

Graf jest nieskierowany, więc dla każdej 'trasy':
\(\displaystyle{ 1 \to (y_1^\prime \in Y) \to (x_2 \in X) \to (y_2^\prime \in Y) \to ... \to (x_n \in X) \to (y_n^\prime \in Y) \to 1}\)
istnieje 'trasa' symetryczna:
\(\displaystyle{ 1 \leftarrow (y_1^\prime \in Y) \leftarrow (x_2 \in X) \leftarrow (y_2^\prime \in Y) \leftarrow ... \leftarrow (x_n \in X) \leftarrow (y_n^\prime \in Y) \leftarrow 1}\)
gdzie:
\(\displaystyle{ y_1^\prime = y_n^\prime, y_2^\prime = y_{n-1}^\prime, ... \\
x_2 = x_n, x_3 = x_{n-1}, ...}\)
To redukuje nam liczbę cykli o połowę i daje ostatecznie: \(\displaystyle{ \frac{n!(n-1)!}{2}}\)

miodzio1988, chętnie zobaczę Twoje rozwiązanie do tego zadania.

[miodzio1988]

No bardzo podobne
Mamy dwie klasy. W każdej jest \(\displaystyle{ n}\) wierzchołków. Wybieramy dowolny wierzchołek z klasy np \(\displaystyle{ X}\). Możemy go wybrać na \(\displaystyle{ n}\) sposobów. Ten wierzchołek idzie do wierzchołka z klasy \(\displaystyle{ Y}\) . Taki wierzchołek też możemy wybrać na \(\displaystyle{ n}\) sposobów. I tak dalej i tak dalej.
Odpowiedz to:
\(\displaystyle{ n \cdot n \cdot (n-1) \cdot (n-1) \cdot (n-2) \cdot (n-2) \cdot ... \cdot 1 \cdot 1}\)
Zastanawiam się nad tą trasą symetryczną o ktorej wspomnialeś...No, ale o symetrii tu nie może być mowy. każdy wierzchołek ma swój numerek, więc nieskierowanie grafu nie ma tutaj znaczenia. Rozwiązanie jednak zaliczam Trudne nie było, nie? Zdam egzamin z analizy to wrzucę jakieś inne fajne zadanka
Pozdrawiam

[Szemek]

Dla grafu \(\displaystyle{ K_{2,2}}\)
Niech:
\(\displaystyle{ X = \{1,2\} \\
Y = \{A,B\}}\)
Wszystkie 'trasy':
\(\displaystyle{ \text{1A2B1} \\
\text{1B2A1}}\)
Edit:
Trasy są symetryczne.
Czyli mamy tylko jeden unikalny cykl Hamiltona.
Dla grafu \(\displaystyle{ K_{3,3}}\)
Niech:
\(\displaystyle{ X = \{1,2,3\} \\
Y = \{A,B,C\}}\)
Wszystkie 'trasy':
\(\displaystyle{ \begin{array}{ccc}
\boxed{1} \text{1A2B3C1} & \boxed{5} \text{1B2A3C1} & \boxed{6} \text{1C2A3B1} \\
\boxed{2} \text{1A2C3B1} & \boxed{4} \text{1B2C3A1} & \boxed{3} \text{1C2B3A1} \\
\boxed{3} \text{1A3B2C1} & \boxed{6} \text{1B3A2C1} & \boxed{5} \text{1C3A2B1} \\
\boxed{4} \text{1A3C2B1} & \boxed{2} \text{1B3C2A1} & \boxed{1} \text{1C3B2A1}\end{array}}\)

Tymi samym numerkami w kwadracie oznaczyłem 'trasy' dla których sekwencja jednej jest taka sama jak w odwrotnej kolejności sekwencja drugiej.
Czyli mamy 6 unikalnych cykli Hamiltona.
O taką symetryczność mi chodzi.

Zadanie trudne nie było Ale pora brać się za analizę, bo też nade mną wisi.
Pozdrawiam.

[miodzio1988]

Dla grafu \(\displaystyle{ K_{2,2}}\)
Niech:
\(\displaystyle{ X = \{1,2\} \\
Y = \{A,B\}}\)
Wszystkie 'trasy':
\(\displaystyle{ \text{1A2B1} \\
\text{1B2A1}}\)

\(\displaystyle{ \text{1A2B1} \\
\text{1B2A1}}\)
\(\displaystyle{ \text{2A1B2} \\
\text{2B1A2}}\)
czyli są 4 trasy
Tylko teraz moglibyśmy zacząć od wierzchołków z klasy \(\displaystyle{ Y}\) również... coś jest nie tak ale ja spadam się uczyc po sesji o tym pomyślimy
powodzenia :P

[Szemek]

\(\displaystyle{ \text{1A2B1} \\
\text{1B2A1}}\)
\(\displaystyle{ \text{2A1B2} \\
\text{2B1A2}}\)
czyli są 4 trasy
Tylko teraz moglibyśmy zacząć od wierzchołków z klasy \(\displaystyle{ Y}\) również... coś jest nie tak

Uzupełniłem poprzedni post.

miodzio1988, w grafie \(\displaystyle{ K_{2,2}}\) mamy tylko jeden unikalny cykl Hamiltona. Nieważne od którego wierzchołka zaczniemy ani w którą stronę będziemy iść. To co napisałeś, to jest tylko rotacja kolejności.

[miodzio1988]

No właśnie tutaj jest problem. Różnica w naszych definicjach Dla mnie "taka rotacja " jest już innym grafem
Sorry, że dopiero teraz piszę, ale egzamin... Nie ma co się dłużej nad zadaniem rozwodzić

EOT ;]