Knight liikkua kaavio

Knight liikkua kaavio
Ritariliikekaavio 8 × 8
Huiput	nm
kylkiluut	4 min - 6( m + n ) + 8
Ympärysmitta	4 (jos n ≥ 3, m ≥ 5)

Graafiteoriassa ritarien liikkeiden kuvaaja on graafi, joka kuvaa ritarin kaikkia mahdollisia liikkeitä shakkilaudalla – jokainen kärkipiste vastaa laudan solua ja reunat vastaavat mahdollisia liikkeitä [ 1] .

Kun ritari liikkuu kaavion kokoisella laudalla, pisteiden lukumäärä on . Lautassa kärkien lukumäärä on ja reunojen määrä on . $n \ kertaa m$ $nm$ $n\ kertaa n$ $n^{2}$ $4(n-2)(n-1)$

Hamiltonin polun löytäminen ritarin liikegraafille on ongelma ratasta kävelemässä laudan ympäri [1] . Schwenkin lause ( Schwenk ) antaa niiden shakkilaudojen mitat, joilla ritari voi ohittaa [2] .

Katso myös

Muistiinpanot

↑ 1 2 Orin Averbach, Orin Chein. Ongelmanratkaisu virkistysmatematiikan avulla. - Dover, 1980. - ISBN 9780486131740 .
↑ John J. Watkins. Kaiken kaikkiaan: Shakkilautaongelmien matematiikka. Paradokseja, hämmennystä ja matemaattisia pulmia vakavalle pään raapijalle. - Princeton University Press, 2012. - s. 44 . — ISBN 9780691154985 .