| 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
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 5630 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:chromaticIndex
| |
| dbp:chromaticNumber
| |
| dbp:girth
| |
| dbp:imageCaption
| |
| dbp:name
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
