Chessboard graphs#
The methods defined here appear in sage.graphs.graph_generators
.
AUTHORS:
David Coudert (2012)
- sage.graphs.generators.chessboard.BishopGraph(dim_list, radius=None, relabel=False)#
Return the \(d\)-dimensional Bishop Graph with prescribed dimensions.
The 2-dimensional Bishop Graph of parameters \(n\) and \(m\) is a graph with \(nm\) vertices in which each vertex represents a square in an \(n \times m\) chessboard, and each edge corresponds to a legal move by a bishop.
The \(d\)-dimensional Bishop Graph with \(d >= 2\) has for vertex set the cells of a \(d\)-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a bishop in any pairs of dimensions.
The Bishop Graph is not connected.
INPUT:
dim_list
– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardradius
– integer (default:None
); by setting the radius to a positive integer, one may decrease the power of the bishop to at mostradius
steps.relabel
– boolean (default:False
); indicates whether the vertices must be relabeled as integers
EXAMPLES:
The (n,m)-Bishop Graph is not connected:
sage: G = graphs.BishopGraph( [3, 4] ) sage: G.is_connected() False
The Bishop Graph can be obtained from Knight Graphs:
sage: for d in range(3,12): # long time ....: H = Graph() ....: for r in range(1,d+1): ....: B = graphs.BishopGraph([d,d],radius=r) ....: H.add_edges( graphs.KnightGraph([d,d],one=r,two=r).edges(sort=False) ) ....: if not B.is_isomorphic(H): ....: print("that's not good!")
- sage.graphs.generators.chessboard.ChessboardGraphGenerator(dim_list, rook=True, rook_radius=None, bishop=True, bishop_radius=None, knight=True, knight_x=1, knight_y=2, relabel=False)#
Return a Graph built on a \(d\)-dimensional chessboard with prescribed dimensions and interconnections.
This function allows to generate many kinds of graphs corresponding to legal movements on a \(d\)-dimensional chessboard: Queen Graph, King Graph, Knight Graphs, Bishop Graph, and many generalizations. It also allows to avoid redundant code.
INPUT:
dim_list
– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardrook
– boolean (default:True
); indicates whether the chess piece is able to move as a rook, that is at any distance along a dimensionrook_radius
– integer (default:None
); restriction on the rook-like movements to distance at mostrook_radius
bishop
– boolean (default:True
); indicates whether the chess piece is able to move like a bishop, that is along diagonalsbishop_radius
– integer (default:None
); restriction on the bishop-like movements to distance at mostbishop_radius
knight
– boolean (default:True
); indicating whether the chess piece is able to move like a knightknight_x
– integer (default:1
); indicates the number on steps the chess piece moves in one dimension when moving like a knightknight_y
– integer (default:2
); indicates the number on steps the chess piece moves in the second dimension when moving like a knightrelabel
– boolean (default:False
); indicates whether the vertices must be relabeled as integers
OUTPUT:
A Graph build on a \(d\)-dimensional chessboard with prescribed dimensions, and with edges according given parameters.
A string encoding the dimensions. This is mainly useful for providing names to graphs.
EXAMPLES:
A \((2,2)\)-King Graph is isomorphic to the complete graph on 4 vertices:
sage: G, _ = graphs.ChessboardGraphGenerator( [2,2] ) sage: G.is_isomorphic( graphs.CompleteGraph(4) ) True
A Rook’s Graph in 2 dimensions is isomorphic to the Cartesian product of 2 complete graphs:
sage: G, _ = graphs.ChessboardGraphGenerator([3,4], rook=True, rook_radius=None, bishop=False, knight=False) sage: H = (graphs.CompleteGraph(3)).cartesian_product(graphs.CompleteGraph(4)) sage: G.is_isomorphic(H) True
- sage.graphs.generators.chessboard.KingGraph(dim_list, radius=None, relabel=False)#
Return the \(d\)-dimensional King Graph with prescribed dimensions.
The 2-dimensional King Graph of parameters \(n\) and \(m\) is a graph with \(nm\) vertices in which each vertex represents a square in an \(n \times m\) chessboard, and each edge corresponds to a legal move by a king.
The d-dimensional King Graph with \(d >= 2\) has for vertex set the cells of a d-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a king in either one or two dimensions.
All 2-dimensional King Graphs are Hamiltonian, biconnected, and have chromatic number 4 as soon as both dimensions are larger or equal to 2.
INPUT:
dim_list
– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardradius
– integer (default:None
); by setting the radius to a positive integer, one may increase the power of the king to at leastradius
steps. When the radius equals the higher size of the dimensions, the resulting graph is a Queen Graph.relabel
– boolean (default:False
); indicates whether the vertices must be relabeled as integers
EXAMPLES:
The \((2,2)\)-King Graph is isomorphic to the complete graph on 4 vertices:
sage: G = graphs.QueenGraph( [2, 2] ) sage: G.is_isomorphic( graphs.CompleteGraph(4) ) True
The King Graph with large enough radius is isomorphic to a Queen Graph:
sage: G = graphs.KingGraph( [5, 4], radius=5 ) sage: H = graphs.QueenGraph( [4, 5] ) sage: G.is_isomorphic( H ) True
Also True in higher dimensions:
sage: G = graphs.KingGraph( [2, 5, 4], radius=5 ) sage: H = graphs.QueenGraph( [4, 5, 2] ) sage: G.is_isomorphic( H ) True
- sage.graphs.generators.chessboard.KnightGraph(dim_list, one=1, two=2, relabel=False)#
Return the d-dimensional Knight Graph with prescribed dimensions.
The 2-dimensional Knight Graph of parameters \(n\) and \(m\) is a graph with \(nm\) vertices in which each vertex represents a square in an \(n \times m\) chessboard, and each edge corresponds to a legal move by a knight.
The d-dimensional Knight Graph with \(d >= 2\) has for vertex set the cells of a d-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a knight in any pairs of dimensions.
The \((n,n)\)-Knight Graph is Hamiltonian for even \(n > 4\).
INPUT:
dim_list
– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardone
– integer (default:1
); indicates the number of steps in the first dimensiontwo
– integer (default:2
); indicates the number of steps in the second dimensionrelabel
– boolean (default:False
); indicates whether the vertices must be relabeled as integers
EXAMPLES:
The \((3,3)\)-Knight Graph has an isolated vertex:
sage: G = graphs.KnightGraph( [3, 3] ) sage: G.degree( (1,1) ) 0
The \((3,3)\)-Knight Graph minus vertex (1,1) is a cycle of order 8:
sage: G = graphs.KnightGraph( [3, 3] ) sage: G.delete_vertex( (1,1) ) sage: G.is_isomorphic( graphs.CycleGraph(8) ) True
The \((6,6)\)-Knight Graph is Hamiltonian:
sage: G = graphs.KnightGraph( [6, 6] ) sage: G.is_hamiltonian() # needs sage.numerical.mip True
- sage.graphs.generators.chessboard.QueenGraph(dim_list, radius=None, relabel=False)#
Return the \(d\)-dimensional Queen Graph with prescribed dimensions.
The 2-dimensional Queen Graph of parameters \(n\) and \(m\) is a graph with \(nm\) vertices in which each vertex represents a square in an \(n \times m\) chessboard, and each edge corresponds to a legal move by a queen.
The \(d\)-dimensional Queen Graph with \(d >= 2\) has for vertex set the cells of a \(d\)-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a queen in either one or two dimensions.
All 2-dimensional Queen Graphs are Hamiltonian and biconnected. The chromatic number of a \((n,n)\)-Queen Graph is at least \(n\), and it is exactly \(n\) when \(n\equiv 1,5 \bmod{6}\).
INPUT:
dim_list
– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardradius
– integer (default:None
); by setting the radius to a positive integer, one may reduce the visibility of the queen to at mostradius
steps. When radius is 1, the resulting graph is a King Graph.relabel
– boolean (default:False
); indicates whether the vertices must be relabeled as integers
EXAMPLES:
The \((2,2)\)-Queen Graph is isomorphic to the complete graph on 4 vertices:
sage: G = graphs.QueenGraph([2, 2]) sage: G.is_isomorphic(graphs.CompleteGraph(4)) True
The Queen Graph with radius 1 is isomorphic to the King Graph:
sage: G = graphs.QueenGraph([4, 5], radius=1) sage: H = graphs.KingGraph([5, 4]) sage: G.is_isomorphic(H) True
Also True in higher dimensions:
sage: G = graphs.QueenGraph([3, 4, 5], radius=1) sage: H = graphs.KingGraph([5, 3, 4]) sage: G.is_isomorphic(H) True
The Queen Graph can be obtained from the Rook Graph and the Bishop Graph:
sage: for d in range(3,12): # long time ....: for r in range(1,d+1): ....: G = graphs.QueenGraph([d,d],radius=r) ....: H = graphs.RookGraph([d,d],radius=r) ....: B = graphs.BishopGraph([d,d],radius=r) ....: H.add_edges(B.edges(sort=False)) ....: if not G.is_isomorphic(H): ....: print("that's not good!")
- sage.graphs.generators.chessboard.RookGraph(dim_list, radius=None, relabel=False)#
Return the \(d\)-dimensional Rook’s Graph with prescribed dimensions.
The 2-dimensional Rook’s Graph of parameters \(n\) and \(m\) is a graph with \(nm\) vertices in which each vertex represents a square in an \(n \times m\) chessboard, and each edge corresponds to a legal move by a rook.
The \(d\)-dimensional Rook Graph with \(d >= 2\) has for vertex set the cells of a \(d\)-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a rook in any of the dimensions.
The Rook’s Graph for an \(n\times m\) chessboard may also be defined as the Cartesian product of two complete graphs \(K_n \square K_m\).
INPUT:
dim_list
– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardradius
– integer (default:None
); by setting the radius to a positive integer, one may decrease the power of the rook to at mostradius
steps. When the radius is 1, the resulting graph is a \(d\)-dimensional grid.relabel
– boolean (default:False
); indicates whether the vertices must be relabeled as integers
EXAMPLES:
The \((n,m)\)-Rook’s Graph is isomorphic to the Cartesian product of two complete graphs:
sage: G = graphs.RookGraph( [3, 4] ) sage: H = ( graphs.CompleteGraph(3) ).cartesian_product( graphs.CompleteGraph(4) ) sage: G.is_isomorphic( H ) True
When the radius is 1, the Rook’s Graph is a grid:
sage: G = graphs.RookGraph( [3, 3, 4], radius=1 ) sage: H = graphs.GridGraph( [3, 4, 3] ) sage: G.is_isomorphic( H ) True