3.1.1. cnfgen.families.counting module

Implementation of counting/matching formulas

CountingPrinciple(M, p)

Counting principle

The principle claims that there is a way to partition M elements in sets of size p each.

Parameters:

M : non negative integer

size of the domain

p : positive integer

size of each part

Returns:

cnfgen.CNF

PerfectMatchingPrinciple(G)

Generates the clauses for the graph perfect matching principle.

The principle claims that there is a way to select edges to such that all vertices have exactly one incident edge set to 1.

Parameters:

G : undirected graph