Matching structure and the matching lattice
Matching structure and the matching lattice
复制标题
DOI：
10.1016/0095-8956(87)90021-9
复制
发表时间：
1987-10
期刊：
影响因子：
--
通讯作者：
L. Lovász
中科院分区：
文献类型：
--
作者：
L. Lovász
匹配多面体，即图的完美匹配的凸壳（关联向量），用Edmonds来表征；这一结果是研究多面体组合学的关键，并被用于许多组合算法中。线性船体完美匹配的特点是Naddef， Edmonds， Lovász和Pulleyblank。本文描述了由这些向量生成的格，即完美匹配的所有整数线性组合的集合。从某种意义上说，彼得森图是唯一一个比较难的例子。我们的结果还暗示了特征值不同于0的场上完美匹配的线性壳的表征。主要方法是由Kotzig， Lovász和Plummer开发的分解理论，该理论将每个图分解为许多具有非常好的匹配属性的图，称为砖块。这些砖块中的Petersen图的数量将成为匹配晶格的基本参数。并对分解理论作了一些改进。其中，我们证明了在分解过程中获得的砖块列表与过程中所做的特殊选择无关。
The matching polyhedron, i.e., theconvex hullof (incidence vectors of) perfect matchings of a graph was characterized by Edmonds; this result is the key to a large part of polyhedral combinatorics and is used in many combinatorial algorithms. Thelinear hullof perfect matchings was characterized by Naddef, and by Edmonds, Lovász, and Pulleyblank. In this paper we describe thelatticegenerated by these vectors, i.e., the set of all integer linear combinations of perfect matchings. It turns out that the Petersen graph is, in a sense, the only difficult example. Our results also imply a characterization of the linear hull of perfect matchings over fields of characteristic different from 0. The main method is a decomposition theory developed by Kotzig, Lovász, and Plummer, which breaks down every graph into a number of graphs calledbrickswith very good matching properties. The number of Petersen graphs among these bricks will turn out to be an essential parameter of the matching lattice. Some refinements of the decomposition theory are also given. Among others, we show that the list of bricks obtained during the decomposition procedure is independent of the special choices made during the procedure.