摘要
给出了边矩阵的定义,提出了求解完备匹配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.
出处
《湖南大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2011年第12期72-76,共5页
Journal of Hunan University:Natural Sciences
基金
辽宁省高等学校科学研究项目(20060842)
关键词
完备匹配
完全图
算法
边矩阵
边着色
dual
perfect matching
complete graph
algorithm
edge matrix
edge coloring