论文标题
双方移植物I：梳子的Dulmage-Mendelsohn分解梳子
Bipartite Graft I: Dulmage-Mendelsohn Decomposition for Combs
论文作者
论文摘要
我们为一类称为梳子 - 双方移植物的移植物提供了dulmage-mendelsohn分解的类似物。匹配理论中的dulmage-mendelsohn分解是一种经典的规范结构定理，用于双分部分图。该经典定理的大部分部分位于可分解的两部分图中，即具有完美匹配的二手图。最小加入移植物，也称为最低$ t $ - 图表， 是可分解图中完美匹配的概括。塞伯（Sebö）在他的论文中揭示了梳子双方移植物构成了两种基本的移植物之一，它们是任何移植物的骨架或构件。尤其是，任何双方移植物，即移植物的两部分，都可以被视为梳子双分支移植物的递归组合。在本文中，我们概括了梳子 - 两部分移植物的dulmage-mendelsohn分解。我们还为这种分解显示了一种特性，它是使用Grafts的一般kotzig-lovász分解的特征，这是匹配理论中另一种规范结构定理的已知移植类似物。本文是一系列有关双方移植物的研究。
We provide an analogue of the Dulmage-Mendelsohn decomposition for a class of grafts known as comb-bipartite grafts. The Dulmage-Mendelsohn decomposition in matching theory is a classical canonical structure theorem for bipartite graphs. The substantial part of this classical theorem resides in bipartite graphs that are factorizable, that is, those with a perfect matching. Minimum joins in grafts, also known as minimum $T$-joins in graphs, is a generalization of perfect matchings in factorizable graphs. Sebö revealed in his paper that comb-bipartite grafts form one of the two fundamental classes of grafts that serve as skeletons or building blocks of any grafts. Particularly, any bipartite grafts, that is, bipartite counterpart of grafts, can be considered as a recursive combination of comb-bipartite grafts. In this paper, we generalize the Dulmage-Mendelsohn decomposition for comb-bipartite grafts. We also show for this decomposition a property that is characteristics to grafts using the general Kotzig-Lovász decomposition for grafts, which is a known graft analogue of another canonical structure theorem from matching theory. This paper is the first from a series of studies regarding bipartite grafts.
