| dbo:abstract
|
- In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on the same column (file) as each other, the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape, and can be defined mathematically as the Cartesian product of two complete graphs, as the two-dimensional Hamming graphs, or as the line graphs of complete bipartite graphs. Rook's graphs are highly symmetric, having symmetries taking every vertex to every other vertex. In rook's graphs defined from square chessboards, more strongly, every two edges are symmetric, and every pair of vertices is symmetric to every other pair at the same distance (they are distance-transitive). For chessboards with relatively prime dimensions, they are circulant graphs. With one exception, they can be distinguished from all other graphs by the numbers of triangles each edge belongs to and by the existence of a 4-cycle connecting each nonadjacent pair of vertices. Rook's graphs are perfect graphs, meaning that every subset of chessboard squares can be colored so that no two squares in a row or column have the same color, and so that the number of colors equals the maximum number of squares from the subset in any single row or column (the clique number of an induced subgraph). The graphs formed in this way from subsets of squares in a rook's graph form one of the key components of a decomposition of perfect graphs used to prove the strong perfect graph theorem characterizing all perfect graphs. The independence number and domination number of a rook's graph, or in other words the maximum number of rooks that can be placed so that they do not attack each other or so that they attack all remaining board squares, both equal the smaller of the chessboard's two dimensions, and these are well-covered graphs meaning that placing non-attacking rooks one at a time can never get stuck until a set of maximum size is reached. (en)
- У теорії графів туровий граф — граф, що представляє всі допустимі ходи тури на шахівниці: кожна вершина представляє клітинку на дошці, а ребра — можливі ходи. Турові графи є вкрай симетричними досконалими графами — їх можна описати в термінах числа трикутників, яким належить ребро, та існування циклу довжини 4, що включає будь-які дві несуміжні вершини. (uk)
- В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины. (ru)
|
| rdfs:comment
|
- У теорії графів туровий граф — граф, що представляє всі допустимі ходи тури на шахівниці: кожна вершина представляє клітинку на дошці, а ребра — можливі ходи. Турові графи є вкрай симетричними досконалими графами — їх можна описати в термінах числа трикутників, яким належить ребро, та існування циклу довжини 4, що включає будь-які дві несуміжні вершини. (uk)
- В теории графов ладе́йным гра́фом называется граф, представляющий все допустимые ходы ладьи на шахматной доске — каждая вершина представляет клетку на доске, а рёбра представляют возможные ходы. Ладейные графы являются крайне симметричными совершенными графами — их можно описать в терминах числа треугольников, которым принадлежит ребро и существования цикла длины 4, включающего любые две несмежные вершины. (ru)
- In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on the same column (file) as each other, the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape, and can be defined mathematically as the Cartesian product of two complete graphs, as the two-dimensional Hamming graphs, or as the line graphs of complete bipartite graphs. (en)
|
