# 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_graph`(graph)

Checks if the given data structure is a valid representation of a graph.

Parameters

graph (`Tuple`[`int`, `AbstractSet`[`Tuple`[`int`, `int`]]]) – data structure to check.

Return type

`bool`

Returns

`True` if the given data structure is a valid representation of a graph, `False` otherwise.

`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
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
Returns

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