Undirected distances and the postman-structure of graphs
Undirected distances and the postman-structure of graphs
复制标题
无向距离和图的邮递员结构
DOI：
10.1016/0095-8956(90)90062-5
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
András Sebö
中科院分区：
文献类型：
--
作者：
András Sebö
我们提出了 ±1 加权无向图中距离函数和最短路径的一些性质。这些扩展了一些基本结果，例如匹配、中国邮递员问题和飞机多种商品流动。此外，距离被证明是有效的工具，可以将图的匹配结构推广到与子图相关的结构，这些子图的度数仅具有奇偶性约束（这些称为连接或邮递员集），这是 Lovász 和 Plummer 提出的问题。特殊情况包括将图的匹配结构推广到加权情况。这篇论文的主要结果是 A. Frank 猜想的一个很好的表征（边数呈线性），即从无向图的固定顶点开始的路径的最小权重，没有负电路。该结果包含著名的关于最小“奇连接”和“奇切割”最大包装的极小极大定理（即 Lovász 关于半整数包装的定理及其由 Seymour 以及后来由 Frank 和 Tardos 进行的锐化），并通过构造具有有利属性的“规范”奇切割最大包装来强化它们。这种奇数切割的打包结果是最小奇数连接结构的特征。使用这些，计算出最小奇数连接的 Gallai-Edmonds 类型结构描述。 （Kotzig-Lovàsz 规范划分的推广将出现在即将发表的论文中。）简而言之，±1 加权图中的距离使我们能够以更紧凑的方式处理匹配本身的某些属性，并概括它们，从而在 ±1 加权图的其他一些有趣的特殊情况下提供新的结果。本论文提出了该技术。
We present some properties of the distance function and of shortest paths in ±1-weighted undirected graphs. These extend some basic results, e.g., on matchings, on the Chinese postman problem, and on plane multicommodity flows. Furthermore, distances turn out to be efficient tools to generalize the matching-structure of graphs to a structure related to subgraphs having onlyparity constraints on their degrees(these are called joins or postman sets), a problem posed by Lovász and Plummer. The special cases includethe generalization of the matching-structure of graphs to the weighted case. The main result of the paper isa good characterization (linear in the number of edges), conjectured by A. Frank, of the minimum weights of paths from a fixed vertex of an undirected graph without negative circuits. This result contains the well-known minimax theorems on minimum “odd joins” and maximum packings of “odd cuts” (namely, Lovász's theorem on half integer packings and its sharpening by Seymour and later by Frank and Tardos) and strengthens them by constructing a “canonical” maximum packing of odd cuts with favourable properties. This packing of odd cuts turns out then to be characteristic forthe structure of minimum odd joins. Using these, a Gallai-Edmonds type structural description of minimum odd joins is worked out. (The generalization of the Kotzig-Lovàsz canonical partition will appear in a forthcoming paper.) Briefly, distances in ±1-weighted graphs make it possible for us to treat some properties of matchings themselves in a more compact way, and to generalize them providing new results on some other interesting special cases of ±1-weighted graphs as well. This technique is worked out in the present paper.