Rytířský graf - Knights graph - Wikipedia

Rytířský graf
	rytířský graf
Vrcholy
Hrany	(li a )
Obvod	4 (pokud a )
Vlastnosti	bipartitní
	Tabulka grafů a parametrů

v teorie grafů, a rytířský grafnebo rytířský prohlídkový graf, je graf který představuje všechny legální pohyby rytíř šachy kus na šachovnice. Každý vrchol tohoto grafu představuje čtverec šachovnice a každá hrana spojuje dva čtverce, které jsou rytířským pohybem od sebe navzájem. ${ displaystyle m krát n}$ rytířský graf je rytířský graf ${ displaystyle m krát n}$ šachovnice.^[1]Jeho vrcholy lze reprezentovat jako body Euklidovské letadlo jehož Kartézské souřadnice ${ displaystyle (x, y)}$ jsou celá čísla s ${ displaystyle 1 leq x leq m}$ a ${ displaystyle 1 leq y leq n}$ (body ve středech čtverců šachovnice) a s dvěma víry spojenými hranou, když jsou Euklidovská vzdálenost je ${ displaystyle { sqrt {5}}}$ .

Pro ${ displaystyle m krát n}$ rytířský graf, počet vrcholů je ${ displaystyle nm}$ . Pro ${ displaystyle n krát n}$ rytířský graf, počet vrcholů je ${ displaystyle n ^ {2}}$ a počet hran je ${ displaystyle 4 (n-2) (n-1)}$ .^[2]

A Hamiltonovský cyklus na rytířském grafu je (uzavřeno) rytířské turné.^[1] Šachovnice s lichým počtem čtverců nemá žádnou prohlídku, protože rytířský graf je a bipartitní graf a pouze bipartitní grafy se sudým počtem vrcholů mohou mít hamiltonovské cykly. Rytířskou prohlídku má až na konečně mnoho šachovnic se sudým počtem čtverců; Schwenkova věta poskytuje přesný seznam toho, které z nich dělají a které ne.^[3]

Když je upraven mít toroidní okrajové podmínky (což znamená, že rytíř není blokován hranou hrací plochy, ale pokračuje na opačnou hranu) ${ displaystyle 4 krát 4}$ rytířský graf je stejný jako čtyřrozměrný hyperkrychlový graf.^[3]

Viz také

Reference

^ ^A ^b Averbach, Bonnie; Chein, Orin (1980), Řešení problémů prostřednictvím rekreační matematiky, Dover, s. 195, ISBN 9780486131740.
^ Sloane, N. J. A. (vyd.). „Sequence A033996“. The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.
^ ^A ^b Watkins, John J. (2004), Obecně: Matematika problémů šachovnice. Paradoxy, zmatky a matematické hádanky pro vážného škrábance hlavy, Princeton University Press, s. 44, 68, ISBN 978-0-691-15498-5.

externí odkazy

Weisstein, Eric W. "Rytířský graf". MathWorld.

[ac-1] A ^b Averbach, Bonnie; Chein, Orin (1980), Řešení problémů prostřednictvím rekreační matematiky, Dover, s. 195, ISBN 9780486131740.

[2] Sloane, N. J. A. (vyd.). „Sequence A033996“. The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.

[watkins-3] A ^b Watkins, John J. (2004), Obecně: Matematika problémů šachovnice. Paradoxy, zmatky a matematické hádanky pro vážného škrábance hlavy, Princeton University Press, s. 44, 68, ISBN 978-0-691-15498-5.

[1]

[2]

[3]

Rytířský graf
${ displaystyle 8 krát 8}$ rytířský graf
Vrcholy	${ displaystyle mn}$
Hrany	${ displaystyle 4mn-6 (m + n) +8}$ (li ${ displaystyle n geq 2}$ a ${ displaystyle m geq 2}$ )
Obvod	4 (pokud ${ displaystyle n geq 3}$ a ${ displaystyle m geq 5}$ )
Vlastnosti	bipartitní
Tabulka grafů a parametrů