Disclosing Barriers: A Generalization of the Canonical Partition Based on Lovász's Formulation
Disclosing Barriers: A Generalization of the Canonical Partition Based on Lovász's Formulation
复制标题
揭示障碍：基于 Lovász 公式的规范划分的推广
DOI：
10.1007/978-3-319-03780-6_35
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Nanao Kita
中科院分区：
文献类型：
--
作者：
Nanao Kita
给定一个图，障碍是由Berge公式确定的一组顶点，该公式是描述最大匹配大小的最小-最大定理。障碍的概念在匹配理论的许多上下文中起着重要的作用，因为障碍本质上与最大匹配问题的对偶最优解相一致。在一类特殊的图中，称为基本图，极大障碍族形成顶点的划分;这种划分是由Lovász发现的，称为典型划分。正则划分在匹配理论中产生了许多基本结果，如双耳定理。然而，在非基本图中，极大障碍族从来不形成划分，并且还没有一般图的标准划分。在本文中，利用我们以前的工作，我们给出了一个典型的描述结构的奇极大障碍，一类障碍，包括最大的障碍，一般的图，我们还揭示了奇组件的结构与奇极大障碍。我们的这一结果可以看作是Lovász典型划分的推广。
Given a graph, a barrier is a set of vertices determined by the Berge formula—the min-max theorem characterizing the size of maximum matchings. The notion of barriers plays important roles in numerous contexts of matching theory, since barriers essentially coincides with dual optimal solutions of the maximum matching problem. In a special class of graphs called the elementary graphs, the family of maximal barriers forms a partition of the vertices; this partition was found by Lovász and is called the canonical partition. The canonical partition has produced many fundamental results in matching theory, such as the two ear theorem. However, in non-elementary graphs, the family of maximal barriers never forms a partition, and there has not been the canonical partition for general graphs. In this paper, using our previous work, we give a canonical description of structures of the odd-maximal barriers—a class of barriers including the maximal barriers—for general graphs; we also reveal structures of odd components associated with odd-maximal barriers. This result of us can be regarded as a generalization of Lovász’s canonical partition.