二部图上完美匹配的正交匹配分解

• 作 者: 朱建明 许涛 何新英
• 机 构: 中国科学院研究生院,济南广播电视大学信息技术学院,河北农业大学信息科学与技术学院
• 出 处: 运筹与管理
• 发表日期: 2008年4期
• 关键词: 图论 正交匹配分解 多项式时间算法 二部图 graph theory orthogonal matching decomposition polynomial

给定简单二部图G=（V，E），最大度是k（k≥3），G有一个完美匹配M={e1，e2，…，ek}。称边集E的划分{E1，E2，…，El}是G的一个关于肼的正交匹配分解，如果对每一个El是G的匹配并且包含且仅包含肼中的一条边。在本文中我们将证明对于简单二部图G，存在关于完美匹配肼的正交匹配分解，并给出了求这个分解的多项式时间算法。