和图论与分数图论的若干结果

《和图论与分数图论的若干结果》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、I驵位代码10445学号20021330分类弓Ol57．6彦缘街缸大学y-764187硕士学位论文论文题目和图论与分数图论的若干结果i1浦人姓名导师姓名论文提交时间应用数学王斑粜觥教孥2005年4月芦日独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特鄹加以标注和致谢的地方钋，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得——(注：如没有其他需要特别声明的，本栏可空)或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：王淘是导师签字

2、：学位论文版权使用授权书本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：王缉嚷签字日期：200芗年年月／21：t割醛茕洳．睁W⋯。、签字日期：200，年4月脏日一生壅垣整盔兰巫主堂焦迨塞l和图论与分数图论的若干结果王海棠(山东师范大学数学科学学院，济南，山东，250014)中文摘要本文主要从甄方面研究图并取得了一些结果．本文

3、的第一部分研究和图．1990年Harary[1】提出了和图的概念，从而开始了对利图的研究．令v(c)表示图G的顶点集合，1SI表示集合s中元素的个数．令N(z)表示正整数(整数)集，N(Z)的非空有限子集s的和图G+(s)是图(sF)其t}lttl!∈E当且仅当u+"∈s；一个图G称为(整)和图，若它同构于某个s(_』、(z)f}0和圈．(整)和数一(G)(<(G))是使得Gu，；K，是(整)和图的非负整数”的最小值11．21_慎和图是取ScZ。＼{O)且所有算术运算均取模m(2lSl+1)的和图．一个图C的模和数p(G)是使得GupKl是模和图的孤立点数P的最小值m图GunKi

4、In(懿)f11甄号S称为排斥的(exclusive)，若对每条边“u∈E(G)，u—tⅧ∈s＼17(G)．Gn0{II-Ji耵l数i(G)是使GunKL有排斥和标号的非负整数，t的最小值㈨从实11lfl',J观点来看，和图标号可用作图的压缩表示，即表示图∞数擗结黝．当利川输入图f

5、{J压缩表示来工作时，数据压缩不仅可以节省内存，还可以』JII快某些l到算法的运算速度．目前对和图的研究主要是从一些特殊图类着手，确定它们的和数、怪干¨数与饮干¨数．迄今为止，已经取得了许多成果．在第二章我们研究了图的并及竹十吲类的排斥和数；在第三章中，我们主要研究K。一E(t‘№)的干¨数、整却1数

6、以／支擞fll数，1ifiJ定了剖分轮1％，-和剖分扇E。、L的和数．我们主要得到如下定理定理2．1．1设图Gl，G2是图，L。是G。gE(c，)Kl的排斥和标号，G是其n0孤讪气集(i=1，2)，且lnaxCl与min岛互质，则E(GlUG2)曼￡(G1)+E(G2)一1推论2．1．1设G。是排斥图，G是G：U￡(Gi)Kl的孤立点集(i=1，2)．且IIl；I,XCI与111incb互质，贝4盯(GlUG2)茎盯(G1)+盯(G2)一1．定理2．2．1￡(K。。)=s+r一1(5≥7‘)定理22．2对r≤s，E(Ⅳ¨一E(rK2))：{8—1．Ls+’幽薹塑董盎堂亟主堂焦造塞

7、一2ec只_一Ec五。，，={≥!：一。，；毛三兰≥一。定理2．2．4定理3．1．1定理3．1．2定理3．1．3定理3．2．13≤E((koKI)S4(忆≥3)．口(％，1)=2∞≥3)．口(Fn．1)=2(n≥3)．X十图K3．4一E(3Kj)(B口W3，1)，p=‘=口=2对s>r，，)(K。一E(rK2))0，s>r=i，或s≥3r一4(r≥2)，或37’一5≥s≥2r一1，s是奇数，或；r曼sS3r一5，s是偶数且5Is+1，r—l，r+l曼s≤2r一20或r一1，2r≤s<鼽s是偶数，或；r≤ss3r一5．s是偶数且s+1不能被5整除．定理3．3．1对4曼r

8、s)≠(4，5)，吼+f’一3≤e(Krls—E(，‘尬))兰o(K，，。一E(7‘jr2))≤“十r一3．其中仁『≯掣¨=[(r-3)+-,,／—(r2(r-_3)21)+—8s(r-1)]驴miIl(『舌十半Ⅵ毒+畔[(r--—2(r-2)—-2)]，”【号出写哿圃]推论3．3．1当4≤r