A python program to test whether a graph has a k-flow or not.
Let k > 1
be an integer, let G
be a graph, let D
be an orientation of G
and let phi
be a weight function that associates to each edge of G
a positive integer in the set {1, 2, ..., k - 1}
. The pair (D, phi)
is a (nowhere-zero) k-flow of G
if the sum of the weights of all edges leaving every vertex v
of G
equals the sum of the weights of all edges entering v
, and we call v
balanced. Similarly, we say the pair (D, phi)
is a (nowhere-zero) modular-k-flow, if every vertex v
is balanced modulus k
.
Tutte [1] defined the concept of k-flows as a generalization of the concept of k-face-colourings after observing that, for any planar graph, a k-flow can be obtained from k-face-colouring and vice-versa. Tutte proposed three celebrated conjectures regarding k-flows of graphs, known as the 5-, 4- and 3-Flow Conjectures.
[1] W. T. Tutte. A contribution to the theory of chromatic polynomials. Can. J. Math., 6:80โ91, 1954.
One may use kflow.py
as a standalone library. Its main function (and actually the only one which should be called by the client-side) is has_k_flow
which takes as its two mandatory arguments the number k
representing which of the flows (3, 4, 5 should be used and a graph G
represented by an adjacency list. The function returns a boolean value that is True
if the graph admits a modular-k-flow. If there is a flow, it is accessible through kflow.answer
, which is a list of possibles k-flows found; However, as a current limitation, if there is a modular-k-flow, kflow.answer
will only have the first found k-flow.
The file go.py
is an example of how to read a graph from input and use the k-flow library.
The thm.py
library was developed exclusively for 4-flows. Its main function is the same as the kflow.py
function; However, one should call thm.has_k_flow
instead. It works by identifying set of edges in the graph that could be used as weight 2 edges, such that their removal yields an Eulerian graph. It is exponentially faster than the brute-force approach, but still not extremely fast.