Covering a Graph by Circuits
Covering a Graph by Circuits
复制标题
DOI：
10.1007/3-540-08860-1_21
复制
发表时间：
1978-07
期刊：
影响因子：
--
通讯作者：
A. Itai;M. Rodeh
中科院分区：
文献类型：
--
作者：
A. Itai;M. Rodeh
圈覆盖是覆盖图的所有边的一组圈;它的长度是这些圈的长度之和。在分析灌溉系统时，有时需要找到短路盖。证明了无桥连通无向图中的n个顶点e条边都有一个尺子小于或等于e+2nlogn的回路覆盖.一个概率算法找到这样的覆盖，其预期的运行时间为0（n2），独立的输入图。本文给出了用Rabin提出的一类概率算法求解图论问题的一个例子，如果图中含有两个边不相交的生成树，则存在一个长度至多为e+n-1的回路覆盖.文中还讨论了回路覆盖与中国邮递员问题的关系.证明了存在最短路覆盖比任何最优邮路都长的图。
A circuit cover is a set of circuits which cover all the edges of a graph; its length is the sum of the lengths of the circuits. In analyzing irrigation systems it is sometimes necessary to find a short circuit cover. It is shown that every bridge-free connected undirected graph with n vertices and e edges has a circuit cover the length of which is less than or equal to e+2nlogn. A probabilistic algorithm for finding such a cover is presented; its expected running time is 0(n2), independent of the input graph. This constitutes an example of solving a graph-theoretical problem by a probabilistic algorithm — the class of algorithms introduced by Rabin.If the graph contains two edge-disjoint spanning trees then there exists a circuit cover of length at most e+n-1.The relationship of circuit covers to the Chinese postman problem is also discussed. It is proven that there exist graphs for which the shortest circuit cover is longer than any optimal postman tour.