Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Nowhere-zero flow
Summary
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.
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
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.
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:
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 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 .
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.
Tutte polynomial and Deletion–contraction formula
Let be the number of M-flows on G. It satisfies the deletion–contraction formula:
Combining this with induction we can show is a polynomial in where is the order of the group M. We call 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.