Institute of Mathematics

Abstract:  Let $G$ and $H$ be acyclic, upward bipolarly oriented plane graphs with the same number $n$ of edges. While $G$ can symbolize a flow network, $H$ has only a controlling role. Let $\phi$ and $\psi$ be bijections from $\{1,\dots,n\}$ to the edge set of $G$ and that of $H$, respectively; their role is to define, for each edge of $H$, the corresponding edge of $G$. Let $b$ be an element of an Abelian group $\mathbb A$. An $n$-tuple $(a_1,\dots,a_n)$ of elements of $\mathbb A$ is a solution of the paired-bipolar-graphs problem $P:=(G,H,\phi,\psi,\mathbb A, b)$ if whenever $a_i$ is the "all-or-nothing-flow" capacity of the edge $\phi(i)$ for $i=1,\dots, n$ and $\vec e$ is a maximal directed path of $H$, then by fully exploiting the capacities of the edges corresponding to the edges of $\vec e$ and neglecting the rest of the edges of $G$, we have a flow process transporting $b$ from the source (vertex) of $G$ to the sink of $G$. Let $P':=(H',G',\psi',\phi',\mathbb A, b)$, where $H'$ and $G'$ are the "two-outer-facet" duals of $H$ and $G$, respectively, and $\psi'$ and $\phi'$ are naturally defined. We prove that $P$ and $P'$ have the same solutions. This result implies George Hutchinson's self-duality theorem on submodule lattices.