“Knight's graph”的意思、由来-开放百科全书

词条

Knight's graph

释义

See also
References
External links

{{infobox graph
| name = Knight's graph
| image =
| image_caption =

knight's graph
| vertices =

| edges =

(if

and

)
| chromatic_number =
| chromatic_index =
| girth = 4 (if

and

)
| properties = bipartite
}}

In graph theory, a knight's graph, or a knight's tour graph, is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other.

More specifically, an knight's graph is a knight's graph of an chessboard.^[1]

Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates are integers with and (the points at the centers of the chessboard squares), and with two

vertices connected by an edge when their Euclidean distance is .

For a knight's graph the total number of vertices is simply . For a knight's graph the total number of vertices is simply and the total number of edges is .^[2]

A Hamiltonian cycle on the knight's graph is a (closed) knight's tour.^[1] A chessboard with an odd number of squares has no tour, because the knight's graph is a bipartite graph and only the bipartite graphs with an even number of vertices can have Hamiltonian cycles. All but finitely many chessboards with an even number of squares have a knight's tour; Schwenk's theorem provides an exact listing of which ones do and which do not.^[3]

When it is modified to have toroidal boundary conditions (meaning that a knight is not blocked by the edge of the board, but instead continues onto the opposite edge) the knight's graph is the same as the four-dimensional hypercube graph.^[3]

References

1. ^¹{{citation|title=Problem Solving Through Recreational Mathematics|first1=Bonnie|last1=Averbach|first2=Orin|last2=Chein|publisher=Dover|year=1980|isbn=9780486131740|page=195|url=https://books.google.com/books?id=xRJxJ7L9sq8C&pg=PA195}}.
2. ^{{Cite OEIS|A033996}}
3. ^¹{{citation|title=Across the Board: The Mathematics of Chessboard Problems. Paradoxes, perplexities, and mathematical conundrums for the serious head scratcher|first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|isbn=978-0-691-15498-5|pages=44, 68|url=https://books.google.com/books?id=EQSPm1MPKJUC&pg=PA44}}.

External links

{{MathWorld|title=Knight Graph|id=KnightGraph}}

2 : Mathematical chess problems|Parametric families of graphs

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

See also

References

External links