Matematické Fórum

oglop · 28. 11. 2013 12:51

Dobry den, potreboval bych trochu poradit s touhle ulohou

Co je hamiltonovský graf?
Kolik různých hamiltonovských cyklů má kompletní graf $K_n$ ?
Dva hamiltonovské cykly považujeme za stejné, procházejí-li stejnými vrcholy ve stejném pořadí. Tj. cyklus $v_1 ,v_2 ,v_3 ,v_4$ považujeme za stejný jako cyklus $v_2 ,v_3 ,v_4 ,v_1$ , ale různý od cyklů $v_1 ,v_4 ,v_3 ,v_2$
(je opačně orientovaný) a $v_1 ,v_4 ,v_2 ,v_3$ (má prohozené pořadí vrcholů).

odpoved na 1. otazku: Graf, ve kterém existuje \textit{hamiltonovský cyklus}, se nazývá hamiltonovský graf

Odpoved 2:
Jesli jsem to pochopil tak na grafu $K_3$ je tech cyklu muze byt 2
$v1, v2, v3$ , $v3, v2, v1$
Takze na grafu $K_4$ jich bude kolik?
protoze mezi vrcholy $v1 a v4$ jsou 4
$1234 X 4321$
$1342 X 2431$
z tohoto se da uvazovat ze mezi libovolnymi 2 vrcholy budou 4 hamiltonovske cykly
Da se rict ze na $n$ vrcholech bude $(n-2)! \cdot 2$ , $(n-2)!$ protoze muzu vychazet z jakeho koli bodu daneho cyklu a $\cdot 2$ protoze cyklus v opacnem poradi je jiny?

petrkovar · 28. 11. 2013 13:20

↑ oglop:K odpovědi 1. a co je to ten hamiltonovský cyklus?
K odpověd 2: A co cyklus $1 4 2 3$ ?

oglop · 28. 11. 2013 17:32 — Editoval oglop (29. 11. 2013 14:02)

petrkovar napsal(a):
↑ oglop:K odpovědi 1. a co je to ten hamiltonovský cyklus?
K odpověd 2: A co cyklus $1 4 2 3$ ?

hamiltonovský cyklus je cyklus ktery projde vsemi vrcholy prave jednou - to tam jeste dopisu, at tam mam tedy vsechny detaily

cyklu $1423$ jsem si nevsiml,
$1234 = O$
$1324 = \infty$
$1423 = 8$

jsou 3 cykly 1 smerem

... zmenil jsem pristup uplne, musim si to promyslet aby to slo rozumne napsat.

co takhle?

Hamiltonovsky cyklus na $n$ vrcholech je posloupnost $n$ cisel, ja tedy je muzu seradit $n!$ zpusoby, tim se mi tam zapociaji i cykly zacinajici na jednom z vrcholu, ktery uz v danem cyklu je.
Takze musim dostat pryc vrcholy, ktere ten cyklus uz obsahuje. To bych mohl udelat tak ze
pocet moznosti v 1 cyklu vydelim poctem vrcholu v nem obsazenych.
$\frac{n!}{n} = (n-1)!$ a to je pocet vsech hamiltonovskych cyklu na grafu $K_n$ .