K_v的完备匹配M_i的算法  

Algorithms of Determining Any Perfect Matching M_i of K_v

作　　者：郑长波[1] 李晓毅[2] 侴万禧[3] 

机构地区：[1]大连海洋大学职业技术学院,辽宁大连116300 [2]沈阳师范大学数学与系统科学学院,辽宁沈阳110034 [3]安徽理工大学土木建筑学院,安徽淮南232001

出　　处：《湖南大学学报（自然科学版）》2011年第12期72-76,共5页Journal of Hunan University:Natural Sciences

基　　金：辽宁省高等学校科学研究项目(20060842)

摘　　要：给出了边矩阵的定义,提出了求解完备匹配Mi的2种算法.其中算法A是利用边矩阵K2′n的Δ(G)-边着色求Mi,算法B是利用边矩阵K2′n的2×2子矩阵划分及完全图Kn的n-1个完备匹配Mi′的求解,再求Mi.介绍了用算法A构造循环赛图K(2i0)的过程和用算法B构造循环赛图K(2i0)的过程.A definition of edge-matrix was given. And two algorithms for determining perfect matching Mi were proposed, of which the algorithm A is determined by using Δ（G）-edge coloring of edge-matrix K′2n, and the algorithm B to perfectly match Mi is determined by partitioning edge-matrix K′v into 2×2 sub matrix and also by solving n-1 perfect matching M′i of a complete graph Kn .The procedures of constructing round-robin tournament K（i）20 by using the algorithm A and using algorithm B were presented respectively.

关 键 词：完备匹配 完全图 算法 边矩阵 边着色 

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