Рыцарлар графигі - Knights graph - Wikipedia

Найттың графигі
	рыцарлар графигі
Тік
Шеттер	(егер және )
Гирт	4 (егер және )
Қасиеттері	екі жақты
	Графиктер мен параметрлер кестесі

Жылы графтар теориясы, а рыцарлар графигінемесе а рыцарьлардың тур графигі, Бұл график барлық заңды қадамдарын білдіреді рыцарь шахмат дана үстінде шахмат тақтасы. Әрқайсысы шың Бұл график шахмат тақтасының квадратын бейнелейді және әр шеті рыцарьлардың бір-бірінен алшақ жүрген екі квадратын біріктіреді. ${ displaystyle m times n}$ рыцарь графигі - рыцарь графигі ${ displaystyle m times n}$ шахмат тақтасы.^[1]Оның шыңдары -ның нүктелері ретінде ұсынылуы мүмкін Евклидтік жазықтық кімдікі Декарттық координаттар ${ displaystyle (x, y)}$ бар бүтін сандар ${ displaystyle 1 leq x leq m}$ және ${ displaystyle 1 leq y leq n}$ (шахмат тақтасы квадраттарының центріндегі нүктелер), және олар екі бұрылыспен жиекпен байланысқан кезде Евклидтік қашықтық болып табылады ${ displaystyle { sqrt {5}}}$ .

Үшін ${ displaystyle m times n}$ рыцарлар графигі, шыңдар саны ${ displaystyle nm}$ . Үшін ${ displaystyle n times n}$ рыцарлар графигі, шыңдар саны ${ displaystyle n ^ {2}}$ және жиектер саны ${ displaystyle 4 (n-2) (n-1)}$ .^[2]

A Гамильтон циклі рыцарь графикасында (жабық) рыцарь туры.^[1] Тақ саны квадраттары бар шахмат тақтасында тур жоқ, өйткені рыцарь графигі - а екі жақты граф және төбелерінің жұп саны бар екі жақты графиктер ғана Гамильтон циклына ие бола алады. Бірнеше квадрат алаңдары бар көптеген шахмат тақталарынан басқаларында рыцарьлар экскурсиясы бар; Швенк теоремасы қайсысының не істемейтінінің нақты тізімін ұсынады.^[3]

Ол өзгертілген кезде тороидтық шекаралық шарттар (рыцарь тақтаның шетінен бұғатталмай, керісінше қарсы шетіне қарай жүретінін білдіреді) ${ displaystyle 4 times 4}$ рыцарь графигі төрт өлшемдімен бірдей гиперкубтық график.^[3]

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ ^а ^б Авербах, Бони; Чейн, Орин (1980), Рекреациялық математика арқылы есептер шығару, Довер, б. 195, ISBN 9780486131740.
^ Слоан, Н. (ред.). «A033996 реттілігі». The Он-лайн тізбегінің энциклопедиясы. OEIS қоры.
^ ^а ^б Уоткинс, Джон Дж. (2004), Тақта бойынша: шахмат тақтасының есептері. Парадокстар, түсініксіздіктер және маңызды сызаттар үшін математикалық жұмбақтар, Принстон университетінің баспасы, 44, 68 б., ISBN 978-0-691-15498-5.

Сыртқы сілтемелер

Вайсштейн, Эрик В. «Рыцарь графигі». MathWorld.

[ac-1] а ^б Авербах, Бони; Чейн, Орин (1980), Рекреациялық математика арқылы есептер шығару, Довер, б. 195, ISBN 9780486131740.

[2] Слоан, Н. (ред.). «A033996 реттілігі». The Он-лайн тізбегінің энциклопедиясы. OEIS қоры.

[watkins-3] а ^б Уоткинс, Джон Дж. (2004), Тақта бойынша: шахмат тақтасының есептері. Парадокстар, түсініксіздіктер және маңызды сызаттар үшін математикалық жұмбақтар, Принстон университетінің баспасы, 44, 68 б., ISBN 978-0-691-15498-5.

[1]

[2]

[3]

Найттың графигі
${ displaystyle 8 times 8}$ рыцарлар графигі
Тік	${ displaystyle mn}$
Шеттер	${ displaystyle 4mn-6 (m + n) +8}$ (егер ${ displaystyle n geq 2}$ және ${ displaystyle m geq 2}$ )
Гирт	4 (егер ${ displaystyle n geq 3}$ және ${ displaystyle m geq 5}$ )
Қасиеттері	екі жақты
Графиктер мен параметрлер кестесі