Matching theory: subgraphs with degree constraints and other properties
Matching theory: subgraphs with degree constraints and other properties
复制标题
匹配理论：具有度约束和其他属性的子图
DOI：
10.14288/1.0079982
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Y. Nam
中科院分区：
文献类型：
--
作者：
Y. Nam
在这篇论文中，我们考虑了匹配问题的三种推广。第一个问题是给定行和列和的矩阵的存在性。这个问题可以解释为二部图的f-因子问题。著名的存在性定理遵循最大流-最小割定理，但它包含指数数量（行数）的不等式。我们推广了Gale-Ryser定理，得到了指数不等式可化为多项式不等式的条件。第二个问题是一般因素问题。设G =（V，E）是重图. {0，1，2，. . .我们称一个B-因子为G的一个生成子图F，使得对于每个顶点v ∈ V，deg（v）∈ B。一个集合B被称为有一个长度为p 1的间隙，如果存在一个整数k，使得k+ 1，.，k+p B，还有k，k+p+ 1 E B。我们知道，如果我们允许长度大于1的间隙，则该问题是NP完全的。本文将Cornuéjols的算法推广到简单图上，得到了当每个B的间隔不大于2时求B因子的强多项式算法.一个新的增广步行，不需要交替介绍。第三个问题是无平方二因子问题。无平方二因子是其中循环不具有长度4的二因子，即不是平方。我们得到了一个增广路径定理，如Berge的增广路径定理的1-匹配。当G的平方是顶点不相交时，我们也得到了一个求无平方二因子的多项式算法。
In this thesis, three generalizations of the matching problem are considered. The first problem is the existence of matrices with given row and column sums. This problem can be interpreted as the f-factor problem of a bipartite graph. The well-known existence theorem follows from maxfiow-mincut theorem, but it contains an exponential number (in the number of rows) of inequalities. We generalize the Gale-Ryser theorem and obtain some conditions under which this exponential number of inequalities can be reduced to a polynomial number of inequalities. The second problem is the general factor problem. Let G = (V, E) be a multigraph. An arbitrary subset BL, of {O, 1,2,. . . , deg(v)} is assigned to each vertex v E V. We call a B-factor a spanning subgraph F of G such that deg (v) e B for every vertex v e V. A set B is said to have a gap of length p 1 if there exists an integer k such that k+ 1,.•.,k+p B, and yet k,k+p+ 1 E B. It’s known that the problem is NP-complete if we allow gaps of length more than one. We extend the algorithm of Cornuéjols for simple graphs and obtain a strongly polynomial algorithm for finding a B-factor when each B doesn’t have a gap of length 2 or more. A new augmenting walk that need not alternate is introduced. The third problem is the square-free two-factor problem. A square-free two-factor is a two-factor in which the cycles don’t have length 4, i.e. are not squares. We obtain an augmenting path theorem like Berge’s augmenting path theorem for a 1-matching. Also we obtain a polynomial algorithm for finding a square-free two-factor when the squares of G are vertex-disjoint.