文档介绍:大连理工大学硕士学位论文类优美图姓名:于春艳中请学位级别:硕士专业:计算机应用指导教师:杨元生优美图是图论中极有趣的研究课题之一,由于它的趣味性和应用性,从60年代中期一经提出,就得到了人们的重视。对一个给定的简单图令|E(G)]=g,如果存在一个一一映射广XG)f01,2,…,qh使得对所有边血v)wE(G),由fv)=\f(u)-/(v)?所导出的函数E(G)f⑴2,…,?}是一个一一对应,则称f是G的一个杭美标亏,G被称为优美图。优美图在射电天文学、尸射线衍射晶体学、密码学、通讯网络编址、电路设计*整电压发生器设计、导弹控制码设计、同步•机码设计等领域有着广泛的应用额设V是一个固定顶点,把t个长度为n的回路通过公共顶点V相连组成的图记作讣用讣vA訂,…,沿J表示C,卩图第i(i< r)个长度为尢的回路上的顶点/对所有的讥具有nt条边的欧拉图为优美图的充要条件为籾三0,3(mod4),G卩图是欧拉图,因此图优美的必要条件为M-0,3(mod4)^-0,3(mod4)时良C®图是优美的。<5择为偶数时*G⑴图的优美性已经被证明’即已证明与5$是优美图本文对与口严⑴的优美标号进行了研究,并给出了C钳H图的两种优美标号朴为奇数时,回路边数最少的情况即C3©图已经被证明是优美图。本文也研究了G*)图的特性,并给出了它的一种优美标号。本文重点对C,)图的优美性进彳亍了研究,设计了计算机辅助下确定CM图优美标号的算法,给出了图的一种优美标号,并用数学方法严格证明了此优美标号正确,从而证明了G©图是优美图。关键词*优美图;顶点标号:边标号ABSTRACTLetG^(K£)beasimplegraphwith1Tjverticesand[/:F((?)f{0,L2>・_*!e|)beaninjectivemapping・Defineaninducedfunctionf*:E(C?)f⑴2$…,}bysettingff(«>v)=l/(u)^/(v)Iforall(utv)/'maps£onto(U2T.…|£|・oflengthn>3feachwithafixedvertex坯:2,…'letC,"denotethegraphobtainedfromtheunionofthercyclesbyidentifyingthetfixedvertices(vo'=y&…=曲).AnecessaryconditionforanEuleriangraphwithmedgestobegracefulisthat3(mod4),henceanecessaryconditionfortobegracefulisthat