King's graph (original) (raw)
In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an king's graph is a king's graph of an chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an king's graph is a king's graph of an chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs. For an king's graph the total number of vertices is and the number of edges is . For a square king's graph this simplifies so that the total number of vertices is and the total number of edges is . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph. In the drawing of a king's graph obtained from an chessboard, there are crossings, but it is possible to obtain a drawing with fewer crossings by connecting the two nearest neighbors of each corner square by a curve outside the chessboard instead of by a diagonal line segment. In this way, crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every king's graph is a planar graph. However, when both and are at least four, and they are not both equal to four, is the optimal number of crossings. (en) Na teoria dos grafos, um grafo do rei é um grafo que representa todos os movimentos legais da peça de xadrez do rei em um tabuleiro de xadrez, onde cada vértice representa um quadrado em um tabuleiro de xadrez e cada borda é um movimento legal. Mais especificamente, um grafo do rei é um grafo do rei de um tabuleiro de xadrez . É o formado a partir dos quadrados de um tabuleiro de xadrez, fazendo um vértice para cada quadrado e uma borda para cada dois quadrados que compartilham uma borda ou um canto. Também pode ser construído como o produto forte de dois grafos caminho. Para um grafo do rei o número total de vértices é e o número de arestas é . Para um grafo do rei quadrado , o número total de vértices é e o número total de arestas é . A vizinhança de um vértice no grafo do rei corresponde à vizinhança de Moore para autômato celular.Uma generalização do grafo do rei, chamada de kinggraph, é formada a partir de um pela adição de duas diagonais de cada face quadrilateral do grafo quadrado. (pt) В теории графов графом ходов короля называется граф, изображающий все возможные ходы короля на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам. Для графа ходов короля на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется . Окрестность вершины в графе ходов короля соответствует окрестности Мура клеточного автомата.Обобщение графа ходов короля можно получить из рамочного графа (плоского графа, у которого каждая грань является четырёхугольником и каждая внутренняя вершина имеет по меньшей мере четыре соседа) путём добавления двух диагоналей для каждой четырёхугольной грани. (ru) У теорії графів граф ходів короля — граф, що зображує всі можливі ходи короля на шахівниці; кожна вершина відповідає клітинці на дошці, а ребра відповідають можливим ходам. Для графа ходів короля на дошці розміру число вершин дорівнює . Для дошки число вершин дорівнює , а число ребер дорівнює . Окіл вершини в графі ходів короля відповідає околу Мура клітинного автомата. Узагальнення графа ходів короля можна отримати з рамкового графа (плоского графа, в якого кожна грань є чотирикутником і кожна внутрішня вершина має принаймні чотири сусіди), додавши для кожної чотирикутної грані дві діагоналі. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/King's_graph_with_white_king.svg?width=300 |
| dbo:wikiPageID | 4508797 (xsd:integer) |
| dbo:wikiPageLength | 5630 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1120497581 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Queen's_graph dbr:Rook's_graph dbr:Path_graph dbr:Crossing_number_(graph_theory) dbr:Chess_piece dbr:Chessboard dbr:Neighbourhood_(graph_theory) dbr:Strong_product_of_graphs dbr:Graph_(discrete_mathematics) dbr:Lattice_graph dbr:Moore_neighborhood dbc:Parametric_families_of_graphs dbc:Mathematical_chess_problems dbr:Graph_theory dbr:King_(chess) dbr:Knight's_graph dbr:Squaregraph dbr:Chess dbr:Bishop's_graph dbr:Map_graph dbr:Planar_graph |
| dbp:chromaticIndex | when (en) |
| dbp:chromaticNumber | when (en) |
| dbp:girth | when (en) |
| dbp:imageCaption | king's graph (en) |
| dbp:name | King's graph (en) |
| dbp:wikiPageUsesTemplate | dbt:Infobox_graph dbt:Portal-inline dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Parametric_families_of_graphs dbc:Mathematical_chess_problems |
| rdf:type | yago:WikicatMathematicalChessProblems yago:Abstraction100002137 yago:Attribute100024264 yago:Communication100033020 yago:Condition113920835 yago:Difficulty114408086 yago:Graph107000195 yago:Problem114410605 yago:State100024720 yago:VisualCommunication106873252 |
| rdfs:comment | In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an king's graph is a king's graph of an chessboard. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs. (en) Na teoria dos grafos, um grafo do rei é um grafo que representa todos os movimentos legais da peça de xadrez do rei em um tabuleiro de xadrez, onde cada vértice representa um quadrado em um tabuleiro de xadrez e cada borda é um movimento legal. Mais especificamente, um grafo do rei é um grafo do rei de um tabuleiro de xadrez . É o formado a partir dos quadrados de um tabuleiro de xadrez, fazendo um vértice para cada quadrado e uma borda para cada dois quadrados que compartilham uma borda ou um canto. Também pode ser construído como o produto forte de dois grafos caminho. (pt) В теории графов графом ходов короля называется граф, изображающий все возможные ходы короля на шахматной доске — каждая вершина соответствует клетке на доске, а рёбра соответствуют возможным ходам. Для графа ходов короля на доске размера число вершин равняется . Для доски число вершин равняется , а число рёбер равняется . (ru) У теорії графів граф ходів короля — граф, що зображує всі можливі ходи короля на шахівниці; кожна вершина відповідає клітинці на дошці, а ребра відповідають можливим ходам. Для графа ходів короля на дошці розміру число вершин дорівнює . Для дошки число вершин дорівнює , а число ребер дорівнює . (uk) |
| rdfs:label | King's graph (en) Граф ходов короля (ru) Grafo do rei (pt) Граф ходів короля (uk) |
| owl:sameAs | freebase:King's graph yago-res:King's graph wikidata:King's graph dbpedia-hu:King's graph dbpedia-pt:King's graph dbpedia-ru:King's graph dbpedia-uk:King's graph https://global.dbpedia.org/id/4pVgA |
| prov:wasDerivedFrom | wikipedia-en:King's_graph?oldid=1120497581&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/King's_graph_with_white_king.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:King's_graph |
| is dbo:wikiPageRedirects of | dbr:King_graph |
| is dbo:wikiPageWikiLink of | dbr:Queen's_graph dbr:Rook's_graph dbr:Strong_product_of_graphs dbr:Cop-win_graph dbr:Moore_neighborhood dbr:Chebyshev_distance dbr:King_(chess) dbr:Knight's_graph dbr:Map_graph dbr:King_graph |
| is foaf:primaryTopic of | wikipedia-en:King's_graph |
