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