Knight flytta graf

Knight flytta graf
Knight flytta graf 8 × 8
Toppar	nm
revben	4 min - 6( m + n ) + 8
Omkrets	4 (om n ≥ 3, m ≥ 5)

I grafteorin är en graf över riddardrag en graf som visar alla möjliga drag av en riddare på ett schackbräde — varje vertex motsvarar en cell på brädet, och kanter motsvarar möjliga drag [1] .

För en graf över riddarrörelser på ett bräde av storlek är antalet hörn . För en bräda är antalet hörn , och antalet kanter är . $n \ gånger m$ $nm$ $n\ gånger n$ $n^{2}$ $4(n-2)(n-1)$

Att hitta en Hamiltonsk väg för riddarens rörelsegraf är problemet med riddaren som går runt brädet [1] . Schwenks sats ( Schwenk ) ger måtten på de schackbräden som riddaren kan gå förbi [2] .

Se även

Anteckningar

↑ 1 2 Orin Averbach, Orin Chein. Problemlösning genom rekreationsmatematik. - Dover, 1980. - ISBN 9780486131740 .
↑ John J. Watkins. Över hela linjen: The Mathematics of Chessboard Problems. Paradoxer, förvirring och matematiska gåtor för den seriösa huvudskraparen. - Princeton University Press, 2012. - S. 44 . — ISBN 9780691154985 .