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 vertices n_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

bool

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 3-coloring problem of the given graph into a satisfiability problem.

Parameters

graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – graph whose 3-coloring problem to reduce.

Return type

Formula

Returns

A propositional formula that is satisfiable if and only if the given graph is 3-colorable.

propositions.reductions.assignment_to_3coloring(graph, assignment)

Efficiently transforms an assignment to the formula corresponding to the 3-coloring problem of the given graph, to a 3-coloring of the given graph so that the 3-coloring is valid if and only if the given assignment is satisfying.

Parameters
Return type

Mapping[int, int]

Returns

A 3-coloring 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).

propositions.reductions.tricolor_graph(graph)

Computes a 3-coloring of the given graph.

Parameters

graph (Tuple[int, AbstractSet[Tuple[int, int]]]) – graph to 3-color.

Return type

Optional[Mapping[int, int]]

Returns

An arbitrary 3-coloring of the given graph if it is 3-colorable, None otherwise.