A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings
A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings
复制标题
完美匹配一般图的偏序结构和规范划分的推广
DOI：
10.1007/978-3-642-35261-4_12
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Nanao Kita
中科院分区：
文献类型：
--
作者：
Nanao Kita
本文研究了具有完美匹配的一般图的结构。首先，我们揭示了一般图的完美匹配的基本组件之间的偏序结构。我们的第二个结果是一个推广的Kotzig的典型划分分解一般图完美匹配。它包含了一个简短的证明定理的典型分区。这些结果给出的分解是典型的，也就是说，唯一的给定图。我们还表明，这两者之间存在相关性，这些可以在多项式时间内计算。
This paper is concerned with structures of general graphs with perfect matchings. We first reveal a partially ordered structure among elementary components of general graphs with perfect matchings. Our second result is a generalization of Kotzig’s canonical partition to a decomposition of general graphs with perfect matchings. It contains a short proof for the theorem of the canonical partition. These results give decompositions which are canonical, that is, unique to given graphs. We also show that there are correlations between these two and that these can be computed in polynomial time.