Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Nowhere-zero flow
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.