Drogi i cykle

[mol_ksiazkowy]

Wyznaczyć \(\displaystyle{ n}\) rozłącznych dróg Hamiltona w \(\displaystyle{ K_{2n}}\) i \(\displaystyle{ n}\) rozłącznych cykli Hamiltona w \(\displaystyle{ K_{2n+1}}\).

[arek1357]

W \(\displaystyle{ K_{2n+1}}\) cykli Hamiltona rozłącznych parami wychodzi mi:

tyle ile jest liczb względnie pierwszych z \(\displaystyle{ 2n+1}\) ale mniejszych od: \(\displaystyle{ \frac{2n+1}{2} }\)...

Ładnie wychodzi dla liczb pierwszych:\(\displaystyle{ 5, 7}\) ale już dla \(\displaystyle{ 9}\) się sypie i nie wychodzi mi, że jest ich \(\displaystyle{ 4}\) tylko \(\displaystyle{ 3}\)

Każdy taki cykl to permutacja liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 9}\), jednocykliczna... i ciężko wyszukać \(\displaystyle{ 4 }\), żeby nie miały krawędzi wspólnych...

Dla siódemki będzie ich trzy... za to...


Pokaże dla dziewiątki np:

\(\displaystyle{ (1,2,3,4,5,6,7,8,9)}\)

\(\displaystyle{ (1,3,5,7,9,2,4,6,8)}\)

\(\displaystyle{ (1,5,9,4,8,3,7,2,6)}\)

Mamy tu trzy permutacje, między którymi, żadne dwie kolejne pary się nie powtórzą...

I nie znajdę raczej czwartej permutacji w której dziewięć par i żadna się nie powtórzy...

[kerajs]

Każdy taki cykl to permutacja liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 9}\), jednocykliczna... i ciężko wyszukać \(\displaystyle{ 4 }\), żeby nie miały krawędzi wspólnych...

Przykład :
\(\displaystyle{ (1,2,3,4,5,6,7,8,9)}\)
\(\displaystyle{ (1,3,5,7,9,2,4,6,8)}\)
\(\displaystyle{ (1,6,3,9,5,2,8,4,7) \\
(1,4,9,6,2,7,3,8,5)}\)

[arek1357]

A tak faktycznie jest...

Dodano po 23 minutach 8 sekundach:
To sprawa wydaje się być prosta w każdym cyklu o długości:

\(\displaystyle{ 2n+1}\) jest par \(\displaystyle{ 2n+1}\) a wszystkich możliwych par jest w takim układzie:

\(\displaystyle{ {2n+1 \choose 2}=n \cdot (2n+1) }\)

Czyli dokładnie wyjdzie: \(\displaystyle{ n}\) niezależnych cykli nieprzecinających się bo:

\(\displaystyle{ \frac {n \cdot (2n+1)}{2n+1}=n}\)

Na każdy cykl zużywamy \(\displaystyle{ n}\) niezależnych par z puli: \(\displaystyle{ n \cdot (2n+1)}\) - wszystkich par...

[kerajs]

Sądzę, że nie o to chodzi, skoro cykle i drogi opisane w zadaniu muszą wykorzystać wszystkie krawędzie klik aby zaistnieć we wskazanej liczbie.
Przypuszczam że raczej chodzi o wskazanie przepisu jak je wyznaczać.

Przykładowo, w przypadku klik o liczbie pierwszej \(\displaystyle{ 2n+1}\) wierzchołków przepis jest prosty: przykładowe rozłączne cykle to kolejne, co drugie, trzecie,..., n-te poetykietowane wierzchołki. Jednak dla nieparzystych złożonych liczb \(\displaystyle{ 2n+1}\) samych ''gwiaździstych'' cykli nie można użyć, co pokazał przykład z \(\displaystyle{ K_9}\).

PS
Bardzo nie lubię tej nadużywanej przez panie frazy, lecz tu muszę ją napisać: Nie wiem jak ma być, ale na pewno nie tak.

[arek1357]

Pewnie masz rację bo o ilości tych cykli jest już sprawa jasna...
W rzeczy samej sprawa jeszcze do przemyślenia, na pewno ma to związek z rozkładem liczb na czynniki pierwsze...

Dodano po 23 godzinach 8 minutach 51 sekundach:
Dodam tu jeszcze, że w takim grafie pełnym cyklami Hamiltona będą "podgrafy" , których stopień każdego wierzchołka będzie dokładnie dwa,
(Są one złożone z boków i przekątnych wielokąta), jako samodzielny graf o każdym wierzchołku równym dwa będzie to cykl Eulera bo w takim przechodzimy przez wszystkie jego krawędzie...i wracamy do początku, pierwsze dwa łatwo bardzo narysować bo pierwszy składa się z samych boków a drugi z przekątnych pierwszego stopnia:

\(\displaystyle{ (1,3,5,7,...2n-1, 2n+1,2,4,6,...,2n)}\)

Gorzej jest generować pozostałe ...