In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs.
Definitions Let G = (V,E) be a digraph and let M be an abelian group. A map φ: E → M is an M-circulation if for every vertex v ∈ V
∑ e ∈ δ + ( v ) φ ( e ) = ∑ e ∈ δ − ( v ) φ ( e ) , {\displaystyle \sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),}
where δ+(v) denotes the set of edges out of v and δ−(v) denotes the set of edges into v. Sometimes, this condition is referred to as Kirchhoff's law. If φ(e) ≠ 0 for every e ∈ E, we call φ a nowhere-zero flow, an M-flow, or an NZ-flow. If k is an integer and 0 < |φ(e)| < k then φ is a k-flow.
Other notions Let G = (V,E) be an undirected graph. An orientation of E is a modular k-flow if for every vertex v ∈ V we have:
| δ + ( v ) | ≡ | δ − ( v ) | mod k . {\displaystyle |\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.}
Properties The set of M-flows does not necessarily form a group as the sum of two flows on one edge may add to 0. (Tutte 1950) A graph G has an M-flow if and only if it has a |M|-flow. As a consequence, a Z k {\displaystyle \mathbb {Z} _{k}} flow exists if and only if a k-flow exists. As a consequence if G admits a k-flow then it admits an h-flow where h ≥ k {\displaystyle h\geq k} . Orientation independence. Modify a nowhere-zero flow φ on a graph G by choosing an edge e, reversing it, and then replacing φ(e) with −φ(e). After this adjustment, φ is still a nowhere-zero flow. Furthermore, if φ was originally a k-flow, then the resulting φ is also a k-flow. Thus, the existence of a nowhere-zero M-flow or a nowhere-zero k-flow is independent of the orientation of the graph. Thus, an undirected graph G is said to have a nowhere-zero M-flow or nowhere-zero k-flow if some (and thus every) orientation of G has such a flow.
Flow polynomial
Let N M ( G ) {\displaystyle N_{M}(G)} be the number of M-flows on G. It satisfies the deletion–contraction formula:
N M ( G ) = N M ( G / e ) − N M ( G ∖ e ) . {\displaystyle N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).}
Combining this with induction we can show N M ( G ) {\displaystyle N_{M}(G)} is a polynomial in | M | − 1 {\displaystyle |M|-1} where | M | {\displaystyle |M|} is the order of the group M. We call N M ( G ) {\displaystyle N_{M}(G)} the flow polynomial of G and abelian group M. The above implies that two groups of equal order have an equal number of NZ flows. The order is the only group parameter that matters, not the structure of M. In particular N M 1 ( G ) = N M 2 ( G ) {\displaystyle N_{M_{1}}(G)=N_{M_{2}}(G)} if | M 1 | = | M 2 | . {\displaystyle |M_{1}|=|M_{2}|.}
The above results were proved by Tutte in 1953 when he was studying the Tutte polynomial, a generalization of the flow polynomial.
Flow-coloring duality
Bridgeless Planar Graphs There is a duality between k-face colorings and k-flows for bridgeless planar graphs. To see this, let G be a directed bridgeless planar graph with a proper k-face-coloring with colors { 0 , 1 , … , k − 1 } . {\displaystyle \{0,1,\ldots ,k-1\}.} Construct a map
ϕ : E ( G ) → { − ( k − 1 ) , … , − 1 , 0 , 1 , … , k − 1 } {\displaystyle \phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}}
… excerpt ends here. Continue reading the full article.
