[doc] 有关自补图的边着色

[doc] 有关自补图的边着色[doc] 有关自补图的边着色有关自补图的边着色第22卷第4期 2006年l2月焦作师范高等专科学校 JOURNALOFJIAOZUOTEACHERSCOLLEGE Vo1.22.No.4 Dec.20o6 有关自补图的边着色屈长明,种国富 (焦作师范高等专科学校数学系,河南焦作454000) 摘要:本文给出了正则自补图为第二类图的证明. 关键词:自补图;自补置换;边着色中图分类号:0157.5文献标识码:A文章编号:1672—3465(2006)04—0067—02 自补图的...

[doc] 有关自补图的边着色有关自补图的边着色第22卷第4期 2006年l2月焦作师范高等专科学校 JOURNALOFJIAOZUOTEACHERSCOLLEGE Vo1.22.No.4 Dec.20o6 有关自补图的边着色屈长明,种国富 (焦作师范高等专科学校数学系,河南焦作454000) 摘要:本文给出了正则自补图为第二类图的证明. 关键词:自补图;自补置换;边着色中图分类号:0157.5文献标识码:A文章编号:1672—3465(2006)04—0067—02 自补图的研究始于上个世纪60年代,它几乎同时由三位着名的图论专家Ringel,Saeha和Read各自独立地进行了研究,随后有许多着名的图论专家展开对自补图的研究,如 Rao,Clapham,Mathon等.而关于自补图的顶点着色问题在 1979年由ChaoZY(赵忠云)和Jr.whiteheadl等进行了研究. 本文主要证明了正则自补图为第二类图. 1自补图设G=(,E)表示n阶简单图,G的顶点集和边集分别用V(G)和E(G)表示.分别称,l=IV(G)1,e=IE(G)I为图 G的阶和大小,点的度记为d(). 称图G=(,E)为自补图当且仅当G与它的补同构. 有关自补图的性质可参见文献[2]. 引理12设G=(,E)是,l阶自补图,则 1.ni0,1mod(4) 2.设口是G的一个自补置换,则对于任意两点u,? .有盯(u)盯()硅E争u?E 对于自补图的每一个自补置换,我们总可以把它看作若干个不相交轮换的乘积,即口口1’0”2’0”3…口’ 则至多有一个长度为1的轮换,其它的轮换长度可被 4整除.【J 注意:自补图G可能有许多自补置换,实际上,如果足图G的一个自补置换,则对于任意的奇数i,亦是图G的一个自补置换(对于任意的偶数i,是图G的一个自同构). 2图的边着色图G一个k边着色可以看作边集E的一个分类(E., E2,…,),这里E(可能是空的)表示染有颜色i的E的一个子集,一个正常的k边着色是指(E.,E2,…,)中每个E. 均为对集的k边着色.若G有正常的k边着色,则称G是k 边可着色的.无环图的边色数(G)是指使G为k边可着色的那些k的最小值.若(G)=k,则称G是k边色的. 关于图的边着色有一个很着名的Vizing定理_l,它是由 Vizing(1964)和Gupta(1966)各自独立得出的一个结果. A(G)?(G)?A(G)+1 这里A(G)表示G中顶点的最大度. 若(G)=A(G),则称图G为第一类图;若(G):A (G)+1,则称图G为第二类图.判断一个图足第一类还是第二类图为NP-complete问题. 3自补图的边着色我们自然就有这样一个问题,如何确定自补图的色类呢? 我们先观察一些低阶的自补图,如图1所示.图A为唯一的4 阶自补图,记为P4,图B和图C为阶的自补图,分别记为c5和 Bullgraph,显然,Pd和bull图为第一类图,c5为第二类图. 图A图B 图1低阶自补图图C (下转第69页) 收稿日期:2006—05—12 作者简介:屈长明(1957),男,河南焦作人,焦作师范高等专科学校数学系高级讲师,主要从事数学分析及离散数学的教学与研究工作. ? 67? 朱毅军:电磁学中浮环实验的分析詈,这是由于电压正比于电流的时间变化率.表现在数学上,一级微分运算,余弦变负正弦,就出现了电压比电流的相位超前.感抗的大小为,正比于交流电的角频率 ,也许有人怀疑,一个金属环在50赫兹交流电的情况下表现的感抗会很大么?似乎小到可以忽略,可是请注意两点:一是金属环的电阻R也很小,同R相比起来还不能忽略;二是计算金属环的自感系数时,应考虑到它是套在铁芯上的. 因此自感比空心时大多了. 金属环作为一个负载元件,即具有阻抗也具有感抗.因此具有一定的阻抗角:=tg一(oJL/R). 考虑了相位的影响,电流il与i2的相位关系如图3所示.由图可见,在一个周期内,环仍经历了两次斥力,两次吸力,但是斥力的时间比吸力的时间长.因而,电磁力的平均效果是对环的相斥作用.当电磁力与重力平衡时,环呈悬浮状.套在金属环的位置愈是往下,穿过环的磁通就愈多,环的电抗成分愈大,阻抗角就愈大.这样,相斥的电磁力也随之增大.这就是浮环在某个位置平衡的原因. 以上分析提醒我们注意由外磁场的变化引起的感生电动势与感生电流之间可能存在的相位差,楞次定率的适用的条件是阻抗比感抗大的多的情况,不注意这点往往会导致错误的结论. D , 厂,./,,, /, \ 图3电流il与i2相位关系 [参考文献] [1]赵凯华,陈熙谋.电磁学(第二版)[M]. 北京:高等教育出版社, 2oo3. [2]邓飞帆,葛昆龄,王祖凯.普通物理疑难解答[M]. 长沙:湖南科学技术出版社,1991. [3]陈秉乾,舒幼生,胡望雨.电磁学专题研究[M]. 北京:高等教育出版社,2001. [4]贾起民,郑永令,陈暨耀.电磁学[M]. 北京:高等教育出版社, 2m2 (上接第67页) 当IEl>【_IV厂I】?(G)时,我们称图G为过溢(overful1) 图.关于过溢图有一个明显的事实,它一定是奇数阶的. 定理1.过溢(overful1)图为第二类图. 证明:假设(G)=?(G),现给G的一个?(G)边正常染色,由边染色与对集的关系知,G中染以同一种颜色的边数最多为【丁IVI】,则I(G)I?【丁IVI】(G):【】? (G),故G不是过溢图. 定理2.自补图G为过溢的当且仅当G为正则图. 证明:若G为n阶正则自补图,则A(G):(G): 丁n-1,且 e(G)==【号】:【号】?(G), 故G为过溢的. 若G为过溢的,则e(G)=>【号】ix(c)= _ n z - 1A(G) , 故?(G)<号,又G为自补图,有?(G)+(G) =n一1,我们易得Ix(G)=(G):旦. 由定理1和定理2很容易得到下面的结果. 推论1:正则自补图为第二类图. [参考文献] 【1JJ-ABondy,U.S.R.Murty.图论及其应用[M].北京:科学出版社. 1984. [2]许进.自补图理论及其应用[M]. 西安:西安电子科技大学出版社.1999. ? 69?

                    本文档为【[doc] 有关自补图的边着色】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

[doc] 有关自补图的边着色

你可能还喜欢