郑学谦, 乔晓云
(山西大学商务学院,山西 太原 030031)
图论是数学的一个分支,是近年来发展迅速而又应用广泛的一门新兴学科。图的着色问题[1]是图论中十分活跃的研究课题,有着深刻而丰富的理论结果和广泛的实际应用,诸如时间表问题、排课表问题、存储问题等,其理论和方法在离散数学中占有重要地位。Ving[2-3]等很早就研究了多重图的色数问题;唐明元[4]研究了满足2色P4条件完全图的边着色;王俊梅[5]研究了四类圈树的连续边着色;张鑫[6]等研究了环形图的边着色。在此基础上,文中定义了多重图的R(k,n:p)-边着色,并利用正交拉丁方和矩阵的乘法证明了当m≡0(mod2)时,图是R(2,m:4)-边着色图。
定义1[7]M称为r-多重完全图,如果M的任意两个不同的顶点都有r条边。n阶的r-多重完全图记为
定义2[7]多重图m边着色指的是每一条边着给定的m种颜色中的一种,任意两个顶点之间的边着不同颜色。
定义4[8]设n为正整数,S={0,1,2,…,n-1},使得S中的n个元素中的每一个均在每一行出现一次(从而恰好一次)且在每一列出现一次,即每一行和每一列都是S的元素的一个排列,这样组成的n×n矩阵A称为n阶拉丁方。
证明 第1步:利用模n的加法运算得到偶数阶对称拉丁方A2,A4,A6,…,A2n,…
第2步:利用算法构造对角线元素全是0偶阶对称拉丁方。
算法如下:
1)把每一行(除去第一行和最后一行)中要放到最后一列的数找出。这个数的位置根据如下规律确定:
2)把拉丁方A2n中对角线的元素aii和由1)找到的数提出,这行的其它数将向左移1位。
3)将矩阵对角线上的元素放在该行对角线的位置上,将剩下的另一个数放在最后一列。
4)最后一行元素由对称所得。
第3步:将矩阵A2与A2n作运算得出图的边标号,其中(i,j)表示vivj二重边的标号。
,…
…
[1] Bondy J A,Murty U S R.Graph theory with applications[M].New York:The Macmillan Press Ltd.,1976.
[2] Ving V.The chromatic class of multigraph[J].Cybernetics,1965(1):32-41.
[3] Steffen E.A refinement of vings theorem[J].Cybernetics,2000(1):289-291.
[4] 唐明元.满足5色K4条件完全图的边着色[J].上海师范大学学报:自然科学版,2003(3):21-25.
[5] 王俊梅.四类圈树的连续边着色[J].太原师范学院学报:自然科学版,2012(4):4-6.
[6] Zhang Xin,Liu Guizhen.On edge colorings of 1-toroidal graphs[J].数学学报:英文版,2013(7):1421-1428.
[7] 邵泽辉.Ramsey理论中图的构造与计算[D].武汉:华中科技大学,2008.
[8] 冯舜玺.组合数学[M].北京:机械工业出版社,2005.