propositions.reductions module¶
Reduction between computational search problems.

propositions.reductions.
Graph
¶ A graph on a vertex set of the form
(1,
…,
n_vertices
)
, represented by the number of verticesn_vertices
and a set of edges over the vertices.alias of Tuple[int, AbstractSet[Tuple[int, int]]]

propositions.reductions.
is_valid_3coloring
(graph, coloring)¶ Checks whether the given coloring is a valid coloring of the given graph by the colors 1, 2, and 3.
 Parameters
 Return type
 Returns
True
if the given coloring is a valid coloring of the given graph by the colors 1, 2, and 3;False
otherwise.

propositions.reductions.
graph3coloring_to_formula
(graph)¶ Efficiently reduces the 3coloring problem of the given graph into a satisfiability problem.

propositions.reductions.
assignment_to_3coloring
(graph, assignment)¶ Efficiently transforms an assignment to the formula corresponding to the 3coloring problem of the given graph, to a 3coloring of the given graph so that the 3coloring is valid if and only if the given assignment is satisfying.
 Parameters
graph (
Tuple
[int
,AbstractSet
[Tuple
[int
,int
]]]) – graph to produce a 3coloring for.assignment (
Mapping
[str
,bool
]) – assignment to the variables of the formula returned bygraph3coloring_to_formula
(
graph
)
.
 Return type
 Returns
A 3coloring of the given graph by the colors 1, 2, and 3 that is valid if and only if the given assignment satisfies the formula
graph3coloring_to_formula
(
graph
)
.