# 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)[source]#

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 chessboard

• radius – integer (default: None); by setting the radius to a positive integer, one may decrease the power of the bishop to at most radius 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

>>> from sage.all import *
>>> G = graphs.BishopGraph( [Integer(3), Integer(4)] )
>>> 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!")

>>> from sage.all import *
>>> for d in range(Integer(3),Integer(12)):   # long time
...     H = Graph()
...     for r in range(Integer(1),d+Integer(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)[source]#

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 chessboard

• rook – boolean (default: True); indicates whether the chess piece is able to move as a rook, that is at any distance along a dimension

• rook_radius – integer (default: None); restriction on the rook-like movements to distance at most rook_radius

• bishop – boolean (default: True); indicates whether the chess piece is able to move like a bishop, that is along diagonals

• bishop_radius – integer (default: None); restriction on the bishop-like movements to distance at most bishop_radius

• knight – boolean (default: True); indicating whether the chess piece is able to move like a knight

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

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

• relabel – 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

>>> from sage.all import *
>>> G, _ = graphs.ChessboardGraphGenerator( [Integer(2),Integer(2)] )
>>> G.is_isomorphic( graphs.CompleteGraph(Integer(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

>>> from sage.all import *
>>> G, _ = graphs.ChessboardGraphGenerator([Integer(3),Integer(4)], rook=True, rook_radius=None, bishop=False, knight=False)
>>> H = (graphs.CompleteGraph(Integer(3))).cartesian_product(graphs.CompleteGraph(Integer(4)))
>>> G.is_isomorphic(H)
True

sage.graphs.generators.chessboard.KingGraph(dim_list, radius=None, relabel=False)[source]#

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 chessboard

• radius – integer (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 – 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

>>> from sage.all import *
>>> G = graphs.QueenGraph( [Integer(2), Integer(2)] )
>>> G.is_isomorphic( graphs.CompleteGraph(Integer(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

>>> from sage.all import *
>>> G = graphs.KingGraph( [Integer(5), Integer(4)], radius=Integer(5) )
>>> H = graphs.QueenGraph( [Integer(4), Integer(5)] )
>>> 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

>>> from sage.all import *
>>> G = graphs.KingGraph( [Integer(2), Integer(5), Integer(4)], radius=Integer(5) )
>>> H = graphs.QueenGraph( [Integer(4), Integer(5), Integer(2)] )
>>> G.is_isomorphic( H )
True

sage.graphs.generators.chessboard.KnightGraph(dim_list, one=1, two=2, relabel=False)[source]#

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 chessboard

• one – integer (default: 1); indicates the number of steps in the first dimension

• two – integer (default: 2); indicates the number of steps in the second dimension

• relabel – 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

>>> from sage.all import *
>>> G = graphs.KnightGraph( [Integer(3), Integer(3)] )
>>> G.degree( (Integer(1),Integer(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

>>> from sage.all import *
>>> G = graphs.KnightGraph( [Integer(3), Integer(3)] )
>>> G.delete_vertex( (Integer(1),Integer(1)) )
>>> G.is_isomorphic( graphs.CycleGraph(Integer(8)) )
True


The $$(6,6)$$-Knight Graph is Hamiltonian:

sage: G = graphs.KnightGraph( [6, 6] )
sage: G.is_hamiltonian()                                                        # needs sage.numerical.mip
True

>>> from sage.all import *
>>> G = graphs.KnightGraph( [Integer(6), Integer(6)] )
>>> G.is_hamiltonian()                                                        # needs sage.numerical.mip
True

sage.graphs.generators.chessboard.QueenGraph(dim_list, radius=None, relabel=False)[source]#

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 chessboard

• radius – integer (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 – 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

>>> from sage.all import *
>>> G = graphs.QueenGraph([Integer(2), Integer(2)])
>>> G.is_isomorphic(graphs.CompleteGraph(Integer(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

>>> from sage.all import *
>>> G = graphs.QueenGraph([Integer(4), Integer(5)], radius=Integer(1))
>>> H = graphs.KingGraph([Integer(5), Integer(4)])
>>> 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

>>> from sage.all import *
>>> G = graphs.QueenGraph([Integer(3), Integer(4), Integer(5)], radius=Integer(1))
>>> H = graphs.KingGraph([Integer(5), Integer(3), Integer(4)])
>>> 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!")

>>> from sage.all import *
>>> for d in range(Integer(3),Integer(12)):   # long time
...     for r in range(Integer(1),d+Integer(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)[source]#

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 chessboard

• radius – integer (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 – 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

>>> from sage.all import *
>>> G = graphs.RookGraph( [Integer(3), Integer(4)] )
>>> H = ( graphs.CompleteGraph(Integer(3)) ).cartesian_product( graphs.CompleteGraph(Integer(4)) )
>>> 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

>>> from sage.all import *
>>> G = graphs.RookGraph( [Integer(3), Integer(3), Integer(4)], radius=Integer(1) )
>>> H = graphs.GridGraph( [Integer(3), Integer(4), Integer(3)] )
>>> G.is_isomorphic( H )
True