Chessboard graphs

The methods defined here appear in sage.graphs.graph_generators.

  • BishopGraph

  • KingGraph

  • KnightGraph

  • QueenGraph

  • RookGraph

AUTHORS:

  • David Coudert (2012)

sage.graphs.generators.chessboard.BishopGraph(dim_list, radius=None, relabel=False)

Returns 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 – an iterable object (list, set, dict) providing the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboard.

  • radius – (default: None) by setting the radius to a positive integer, one may decrease the power of the bishop to at most radius steps.

  • relabel – (default: False) a boolean set to True if 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() )
....:         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)

Returns 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 – an iterable object (list, set, dict) providing the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboard.

  • rook – (default: True) boolean value indicating if the chess piece is able to move as a rook, that is at any distance along a dimension.

  • rook_radius – (default: None) integer value restricting the rook-like movements to distance at most \(rook_radius\).

  • bishop – (default: True) boolean value indicating if the chess piece is able to move like a bishop, that is along diagonals.

  • bishop_radius – (default: None) integer value restricting the bishop-like movements to distance at most \(bishop_radius\).

  • knight – (default: True) boolean value indicating if the chess piece is able to move like a knight.

  • knight_x – (default: 1) integer indicating the number on steps the chess piece moves in one dimension when moving like a knight.

  • knight_y – (default: 2) integer indicating the number on steps the chess piece moves in the second dimension when moving like a knight.

  • relabel – (default: False) a boolean set to True if 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)

Returns 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 – an iterable object (list, set, dict) providing the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboard.

  • radius – (default: None) by setting the radius to a positive integer, one may increase the power of the king to at least radius steps. When the radius equals the higher size of the dimensions, the resulting graph is a Queen Graph.

  • relabel – (default: False) a boolean set to True if 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)

Returns 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 – an iterable object (list, set, dict) providing the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboard.

  • one – (default: 1) integer indicating the number on steps in one dimension.

  • two – (default: 2) integer indicating the number on steps in the second dimension.

  • relabel – (default: False) a boolean set to True if 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()
True
sage.graphs.generators.chessboard.QueenGraph(dim_list, radius=None, relabel=False)

Returns 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 – an iterable object (list, set, dict) providing the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboard.

  • radius – (default: None) by setting the radius to a positive integer, one may reduce the visibility of the queen to at most radius steps. When radius is 1, the resulting graph is a King Graph.

  • relabel – (default: False) a boolean set to True if 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())
....:         if not G.is_isomorphic(H):
....:            print("that's not good!")
sage.graphs.generators.chessboard.RookGraph(dim_list, radius=None, relabel=False)

Returns 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 – an iterable object (list, set, dict) providing the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboard.

  • radius – (default: None) by setting the radius to a positive integer, one may decrease the power of the rook to at most radius steps. When the radius is 1, the resulting graph is a d-dimensional grid.

  • relabel – (default: False) a boolean set to True if 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