Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
upward plane graph; edge capacity; George Hutchinson's self-duality theorem; lattice identity
upward plane graph; edge capacity; George Hutchinson's self-duality theorem; lattice identity
Summary:
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.
References:
[1] Auer, C., Bachmaier, C., Brandenburg, F. J., Gleissner, A., Hanauer, K.: Upward planar graphs and their duals. Theoret. Comput. Sci. 571 (2015), 36-49. DOI 10.1016/j.tcs.2015.01.003 | MR 3303953 | Zbl 1312.68156
[2] Czédli, G.: A characterization for congruence semi-distributivity. Universal Algebra and Lattice Theory Lecture Notes in Mathematics 1004. Springer, Berlin (1983), 104-110. DOI 10.1007/BFb0063432 | MR 0716177 | Zbl 0525.08006
[3] Czédli, G.: Mal'cev conditions for Horn sentences with congruence permutability. Acta Math. Hung. 44 (1984), 115-124. DOI 10.1007/BF01974108 | MR 0759039 | Zbl 0541.08005
[4] Czédli, G.: Horn sentences in submodule lattices. Acta Sci. Math. 51 (1987), 17-33. MR 0911555 | Zbl 0635.08004
[5] Czédli, G., Day, A.: Horn sentences with (W) and weak Mal'cev conditions. Algebra Univers. 19 (1984), 217-230. DOI 10.1007/BF01190431 | MR 0758319 | Zbl 0549.08003
[6] Czédli, G., Takách, G.: On duality of submodule lattices. Discuss. Math., Gen. Algebra Appl. 20 (2000), 43-49. DOI 10.7151/dmgaa.1004 | MR 1782084 | Zbl 0973.06008
[7] Battista, G. Di, Eades, P., Tamassia, R., Tollis, I. G.: Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. 4 (1994), 235-282. DOI 10.1016/0925-7721(94)00014-X | MR 1303232 | Zbl 0804.68001
[8] Hutchinson, G.: A duality principle for lattices and categories of modules. J. Pure Appl. Algebra 10 (1977), 115-119. DOI 10.1016/0022-4049(77)90014-7 | MR 0460416 | Zbl 0366.18009
[9] Hutchinson, G., Czédli, G.: A test for identities satisfied in lattices of submodules. Algebra Univers. 8 (1978), 269-309. DOI 10.1007/BF02485400 | MR 0469840 | Zbl 0384.06009
[10] Miller, G. L., Naor, J.: Flow in planar graphs with multiple sources and sinks. SIAM J. Comput. 24 (1995), 1002-1017. DOI 10.1137/S0097539789162997 | MR 1350755 | Zbl 0836.68087
[11] Platt, C. R.: Planar lattices and planar graphs. J. Comb. Theory, Ser. B 21 (1976), 30-39. DOI 10.1016/0095-8956(76)90024-1 | MR 0429672 | Zbl 0332.05103
Search
Partner of
