AUTHORS:
This class performs randomized testing for all_graph_colorings.
Since everything else in this file is derived from
all_graph_colorings, this is a pretty good randomized tester for
the entire file. Note that for a graph , G.chromatic_polynomial()
uses an entirely different algorithm, so we provide a good,
independent test.
Calls self.random_all_graph_colorings(). In the future, if other methods are added, it should call them, too.
TESTS:
sage: from sage.graphs.graph_coloring import Test
sage: Test().random(1)
Verifies the results of all_graph_colorings() in three ways:
TESTS:
sage: from sage.graphs.graph_coloring import Test
sage: Test().random_all_graph_colorings(1)
Computes all -colorings of the graph
by casting the graph
coloring problem into an exact cover problem, and passing this
into an implementation of the Dancing Links algorithm described
by Knuth (who attributes the idea to Hitotumatu and Noshita).
The construction works as follows. Columns:
Rows:
Note that this construction results in
entries in the matrix. The Dancing Links algorithm uses a
sparse representation, so if the graph is simple,
and
, this construction runs in
time.
Back-conversion to a coloring solution is a simple scan of the
solutions, which will contain
entries, so
runs in
time also. For most graphs, the conversion
will be much faster – for example, a planar graph will be
transformed for
-coloring in linear time since
.
REFERENCES:
http://www-cs-staff.stanford.edu/~uno/papers/dancing-color.ps.gz
EXAMPLES:
sage: from sage.graphs.graph_coloring import all_graph_colorings
sage: G = Graph({0:[1,2,3],1:[2]})
sage: n = 0
sage: for C in all_graph_colorings(G,3):
... parts = [C[k] for k in C]
... for P in parts:
... l = len(P)
... for i in range(l):
... for j in range(i+1,l):
... if G.has_edge(P[i],P[j]):
... raise RuntimeError, "Coloring Failed."
... n+=1
sage: print "G has %s 3-colorings."%n
G has 12 3-colorings.
TESTS:
sage: G = Graph({0:[1,2,3],1:[2]})
sage: for C in all_graph_colorings(G,0): print C
sage: for C in all_graph_colorings(G,-1): print C
Traceback (most recent call last):
...
ValueError: n must be non-negative.
Returns the minimal number of colors needed to color the
vertices of the graph .
EXAMPLES:
sage: from sage.graphs.graph_coloring import chromatic_number
sage: G = Graph({0:[1,2,3],1:[2]})
sage: chromatic_number(G)
3
sage: G = graphs.PetersenGraph()
sage: G.chromatic_number()
3
Properly colors the edges of a graph. See the URL http://en.wikipedia.org/wiki/Edge_coloring for further details on edge coloring.
INPUT:
OUTPUT:
In the following, is equal to the maximum degree in the graph
g.
EXAMPLE:
sage: from sage.graphs.graph_coloring import edge_coloring
sage: g = graphs.PetersenGraph()
sage: edge_coloring(g, value_only=True) # optional - requires GLPK or CBC
4
Complete graphs are colored using the linear-time round-robin coloring:
sage: from sage.graphs.graph_coloring import edge_coloring
sage: len(edge_coloring(graphs.CompleteGraph(20)))
19
Given a graph, and optionally a natural number , returns
the first coloring we find with at least
colors.
INPUT:
EXAMPLES:
sage: from sage.graphs.graph_coloring import first_coloring
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: first_coloring(G, 3)
[[1, 3], [0], [2]]
Given a graph and a natural number
, returns the number of
-colorings of the graph.
EXAMPLES:
sage: from sage.graphs.graph_coloring import number_of_n_colorings
sage: G = Graph({0:[1,2,3],1:[2]})
sage: number_of_n_colorings(G,3)
12
Returns the number of -colorings of the graph
for
from
to
.
EXAMPLES:
sage: from sage.graphs.graph_coloring import numbers_of_colorings
sage: G = Graph({0:[1,2,3],1:[2]})
sage: numbers_of_colorings(G)
[0, 0, 0, 12, 72]
Computes a round-robin coloring of the complete graph on vertices.
A round-robin coloring of the complete graph on
vertices
(
) is a proper coloring of its edges such that
the edges with color
are all the
plus the
edge
.
If is odd, one obtain a round-robin coloring of the complete graph
through the round-robin coloring of the graph with
vertices.
INPUT:
OUTPUT:
EXAMPLES:
sage: from sage.graphs.graph_coloring import round_robin
sage: round_robin(3).edges()
[(0, 1, 2), (0, 2, 1), (1, 2, 0)]
sage: round_robin(4).edges()
[(0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 2, 0), (1, 3, 1), (2, 3, 2)]
For higher orders, the coloring is still proper and uses the expected number of colors.
sage: g = round_robin(9)
sage: sum([Set([e[2] for e in g.edges_incident(v)]).cardinality() for v in g]) == 2*g.size()
True
sage: Set([e[2] for e in g.edge_iterator()]).cardinality()
9
sage: g = round_robin(10)
sage: sum([Set([e[2] for e in g.edges_incident(v)]).cardinality() for v in g]) == 2*g.size()
True
sage: Set([e[2] for e in g.edge_iterator()]).cardinality()
9
Computes the chromatic number of the given graph or tests its
-colorability. See http://en.wikipedia.org/wiki/Graph_coloring for
further details on graph coloring.
INPUT:
OUTPUT:
EXAMPLE:
sage: from sage.graphs.graph_coloring import vertex_coloring
sage: g = graphs.PetersenGraph()
sage: vertex_coloring(g, value_only=True) # optional - requires GLPK or CBC
3