| dbo:abstract
|
- 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.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 twovertices connected by an edge when their Euclidean distance is . For an knight's graph, the number of vertices is . If and then the number of edges is (otherwise there are no edges). For an knight's graph, these simplify so that the number of vertices is and the number of edges is . A Hamiltonian cycle on the knight's graph is a (closed) knight's tour. A chessboard with an odd number of squares has no tour, because the knight's graph is a bipartite graph and only 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. 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. (en)
- В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам. Для графа ходов коня на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется . Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём. (ru)
- У теорії графів граф ходів коня — граф, що зображує всі можливі ходи коня на шахівниці; кожна вершина відповідає клітинці дошки, а ребра — можливим ходам. Для графа ходів коня на дошці розміру число вершин дорівнює . Для дошки число вершин дорівнює , а число ребер дорівнює . Знаходження гамільтонового шляху для графа ходів коня — це завдання про обхід дошки конем. Теорема Швенка (Schwenk) дає розміри шахових дощок, для яких можливий обхід конем. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3593 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:edges
| |
| dbp:girth
| |
| dbp:id
| |
| dbp:imageCaption
| |
| dbp:name
| |
| dbp:properties
| |
| dbp:title
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- В теории графов графом ходов коня называется граф, изображающий все возможные ходы коня на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам. Для графа ходов коня на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется . Нахождение гамильтонова пути для графа ходов коня — это задача об обходе доски конём. Теорема Швенка (Schwenk) даёт размеры шахматных досок, для которых возможен обход конём. (ru)
- У теорії графів граф ходів коня — граф, що зображує всі можливі ходи коня на шахівниці; кожна вершина відповідає клітинці дошки, а ребра — можливим ходам. Для графа ходів коня на дошці розміру число вершин дорівнює . Для дошки число вершин дорівнює , а число ребер дорівнює . Знаходження гамільтонового шляху для графа ходів коня — це завдання про обхід дошки конем. Теорема Швенка (Schwenk) дає розміри шахових дощок, для яких можливий обхід конем. (uk)
- 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.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 twovertices connected by an edge when their Euclidean distance is . (en)
|
| rdfs:label
|
- Knight's graph (en)
- Граф ходов коня (ru)
- Граф ходів коня (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
