Brick decompositions and the matching rank of graphs
Brick decompositions and the matching rank of graphs
复制标题
DOI：
10.1007/bf02579233
复制
发表时间：
1982-09
期刊：
影响因子：
1.1
通讯作者：
J. Edmonds;L. Lovász;W. Pulleyblank
中科院分区：
文献类型：
--
作者：
J. Edmonds;L. Lovász;W. Pulleyblank
一个图的线性无关完美匹配的个数--或者等价地说完美匹配多面体的维数--在不同的意义上是确定的。首先，它表明，每个线性目标函数可以在多项式时间内优化的完美匹配的事实意味着存在一个多项式时间算法来确定这个集合的维数。这一观察也产生多项式算法，以确定，除其他外，两个拟阵的线性独立的公共基地的数量和线性独立的最大稳定集的数量在无爪或完美的图形。对于完美匹配的情况下，Naddef的极大极小定理的完美匹配多面体的尺寸加强，它是如何分解理论的匹配图可以应用到推导出一个特别简单的公式，这个尺寸。这个公式是基于图的某种分解（我们称之为砖分解）的组成部分的数量。最后，这些结果被应用到获得完美匹配多面体的刻面的描述。
The number of linearly independent perfect matchings of a graph — or, equivalently, the dimension of the perfect matching polytope — is determined in various senses. First it is shown that the fact that every linear objective function can be optimized over the perfect matchings in polynomial time implies the existence of a polynomial-time algorithm to determine the dimension of this set. This observation also yields polynomial algorithms to determine, among others, the number of linearly independent common bases of two matroids and the number of linearly independent maximum stable sets in claw-free or perfect graphs. For the case of perfect matchings, Naddef’s minimax theorem for the dimension of the perfect matching polytope is strengthened and it is shown how the decomposition theory of matchings in graphs can be applied to derive a particularly simple formula for this dimension. This formula is based upon the number of constituents of a certain decomposition of the graph which we call a brick decomposition. Finally, these results are applied to obtain a description of the facets of the perfect matching polytope.