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

Orthogonal Matching Decomposition of Perfect Matching in Simple Bipartite Graph

作　　者：朱建明[1] 许涛[2] 何新英[3] 

机构地区：[1]中国科学院研究生院 [2]济南广播电视大学信息技术学院 [3]河北农业大学信息科学与技术学院

出　　处：《运筹与管理》2008年第4期51-55,共5页Operations Research and Management Science

摘　　要：给定简单二部图G=(V,E),最大度是k(k≥3),G有一个完美匹配M={e1,e2,…,ek}。称边集E的划分{E1,E2,…,El}是G的一个关于M的正交匹配分解,如果对每一个Ei是G的匹配并且包含且仅包含M中的一条边。在本文中我们将证明对于简单二部图G,存在关于完美匹配M的正交匹配分解,并给出了求这个分解的多项式时间算法。Let G = （V,E） be an undirected graph with maximum degreek（k≥3）, and M be a k-matching in G. A partition { E1 ,E2,… ,El} of edge set E is called an orthogonal matching decomposition of M, if each Ei is a matching of G and contains one and only one of an edge of M. In this paper, we will prove that there exit an orthogonal matching decomposition of M in simple bipartite graph, and present a polynomial time algorithm of this decomposition.

关 键 词：图论 正交匹配分解 多项式时间算法 二部图 

分 类 号：O157.5[理学—数学]