Counterexamples for Directed and Node Capacitated Cut-Trees
Counterexamples for Directed and Node Capacitated Cut-Trees
复制标题
有向和节点能力切割树的反例
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
A. Benczúr
中科院分区：
文献类型：
--
作者：
A. Benczúr
我们证明了各种连通性概念都不存在割树，从而指出了Schnorr[SIAM J.Comput.，8(1979)，pp.265-275]和Gusfield and Naor[Networks，21(1991)，pp.505-520]的论文中的错误。访问数/每百万人：Reach for[SIAM J.Appl.Math.，9(1961)，pp.551-560]构造了一棵无向图的割树，它紧凑地表示每对顶点的最小割。这对有向欧拉图有一个直接的推广，参见。访问数/每百万人：Reach for[SIAM J.数学，15(1967)，第168-171页]。Schnorr给出了任意有向图的一个推广。有一个众所周知的从向量连通性到有向边连通性的转换；有向边切割在某种弱意义上对应于顶点切割。Schnorr的结果后来被Gusfield和Naor[8]应用于这样的割树构造。本文通过反例说明，对于有向图，不存在割树，因此Schnorr、Gusfield和Naor的割树结果是错误的。我们的最后一个例子表明，如果不弱化顶点连通性的概念，一般不可能为无向图构造顶点割树。
We show that there is no cut-tree for various connectivity concepts, hence pointing out to errors in the papers of Schnorr [SIAM J. Comput., 8 (1979), pp. 265-275] and Gusfield and Naor [Networks, 21 (1991), pp. 505-520]. Gomory and Hu [SIAM J. Appl. Math., 9 (1961), pp. 551-560] constructed a cut-tree for undirected graphs which compactly represents a minimum cut for each pair of vertices. This has a straightforward generalization to directed Eulerian graphs, cf. Gupta [SIAM J. Appl. Math., 15 (1967), pp. 168-171]. A generalization for arbitrary directed graphs was given by Schnorr. There is a well-known transformation of vetex connectivity to directed edge connectivity; directed edge cuts correspond to vertex cuts in some weak sense. The result of Schnorr was later applied by Gusfield and Naor [8] for such a cut-tree construction. In this paper counterexamples are described to show that for directed graphs there is no cut-tree and therefore the cut-tree results of Schnorr and Gusfield and Naor are incorrect. Our final example shows that, without weakening the notion of vertex connectivity, it is impossible to construct vertex cut-trees for undirected graphs in general.