积网络的线性k荫度.pdf

《积网络的线性k荫度.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级公开UDC学号20150713011青海师范大学硕士学位论文积网络的线性k荫度研究生姓名李贺导师姓名(职称)冶成福，教授申请学位类别硕士学位学科专业名称应用数学研究方向名称组合数学与图论论文提交日期2018年3月论文答辩日期2018年5月学位授予单位青海师范大学学位授予日期2018年6月答辩委员会主席李学良评阅人马海成，毛亚平青青青海海海师师师范范范大大大学学学学学学位位位论论论文文文独独独创创创性性性声声声明明明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果.尽我所知,除了文中特

2、别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得青海师范大学或其它教育机构的学位或证书而使用过的材料.与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意.研究生签名：日期：青青青海海海师师师范范范大大大学学学学学学位位位论论论文文文使使使用用用授授授权权权声声声明明明青海师范大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档,可以采用影印、缩印或其他复制手段保存论文.本人电子文档的内容和纸质论文的内容相一致.除在保密期内

3、的保密论文外,允许论文被查阅和借阅,可以公布（包括刊登）论文的全部或部分内容.论文的公布（包括刊登）授权由青海师范大学研究生部办理.研究生签名：导师签名：日期：积网络的线性k荫度中文摘要线性荫度这个概念最早是由Harary在1970年[3]文献中提出来的.图的线性k−荫度是Habib和Peroche[2]于1983年研究边着色的时候自然推广出来的.一个图的分解就是把原来的图分解成一些子图,原图中每一个边恰好只出现在其中的某一个子图中.假如一个图G分解成G1,G2,...,Gℓ,那么我们就说G1,G2,...,Gℓ分解了

4、图G,或者可以说图G可以被分解成G1,G2,...,Gℓ.因此,将一个图分解成边不相交的生成森林,要求每个森林中的每棵树都是长度不超过k的路,称其为线性k−森林,其生成森林的最少数目叫做该图的线性k−荫度,用lak(G)来表示.通过观察可知线性1−森林是图的匹配数,la1(G)是一个图G的色指数χ′(G).此外,线性荫度la(G)(或者la(G))表示每一部分森林中路∞的长度没有被限制的线性荫度,现在我们对于森林中的路加以限制,就得到了线性k-荫度lak(G).Xue和Zuo[18]对完全多部图的线性n−1荫度做了研究

5、.当前Zuo,He和Xue[19]又对完全图,圈和完全多部图的多种组合的卡式积的线性n−1荫度做了准确的计算.图G和H的卡氏积我们用GH来表示,顶点集为V(GH)=V(G)×V(H),两个顶点(u,v)和(u′,v′)是相邻的,当且仅当u=u′且(v,v′)∈E(H),或者v=v′且(u,u′)∈E(G);图G和H的完全积我们用符号G∨H来表示,顶点集为V(G)∪V(H),边集为E(G)∪E(H)∪{uv

6、u∈V(G),v∈V(H)};图G和H的字典积我们用符号G◦H来表示,顶点集为V(G◦H)=V(G)×V(H)

7、,两个顶点(u,v),(u′,v′)是相邻的，当且仅当uu′∈E(G),或者u=u′且vv′∈E(H).图G和H的强积我们用符号GH来表示,顶点集为V(GH)=V(G)×V(H).两个顶点(u,v)和(u′,v′)是相邻的,当且仅当uu′∈E(G)且v=v′，或者u=u′且vv′∈E(H),或者uu′∈E(G)且vv′∈E(H);图G和H的直积我们用符号G×H来表示,顶点集为V(G×H)=V(G)×V(H).两个顶点(u,v)和(u′,v′)是相邻的,则这两个坐标的投影是相邻的，当且仅当uu′∈E(G)且vv′∈E

8、(H).本文的主要研究结果包括以下几个方面:1.对于两个一般图G和H做卡氏积GH,通过刻画以及反证法,得出了lamax{k,ℓ}(GH)的上下界max{lak(G),laℓ(H)}≤lamax{k,ℓ}(GH)≤lak(G)+laℓ(H).设G1,G2,...,Gr是r个图,并且运用同样的方法推广出了r个图做卡氏I积lamax{k1,k2,...,kr}(G1G2...Gr)的上下界.在本文中,我们也得到了lak(G∨H),lak(G◦H),lak(G×H)和lak(GH)的上下界.2.我们用Gn,m表示

9、有m×n个点的二维网格积图.用PnPm表示n个点的路Pn和m个点路Pm做卡氏积.用Pn◦Pm表示n个点的路Pn和m个点路Pm做字典积.用Pn×Pm表示n个点的路Pn和m个点路Pm做直积.用PnPm表示n个点的路Pn和m个点路Pm做强积.通过限定m,n与k的关系,分别求出了以上二维网格积图的结果.3.我们运用二维网格积图的思路和