学位论文 > 优秀研究生学位论文题录展示

中间P_2-图的边连通性

作　者: 薄祥智
导　师: 孟吉翔
学　校: 新疆大学
专　业: 运筹学与控制论
关键词: 边连通度路图中间P2-图
分类号: O157.5
类　型: 硕士论文
年　份: 2010年
下　载: 5次
引　用: 0次
阅　读: 论文下载

内容摘要

图论中边连通度是用来研究网络可靠性的一个参数,它能比较准确的刻画小规模网络的容错性,其相关结论是研究互联网的拓扑结构的有利工具.为了更好的研究图的边连通度,1932年Whitney[1]提出了线图的概念.关于线图已有很多好的结论.后来,Broersmn和Hoede [2]把线图推广,提出了路图的概念.图G的Pk-路图Pk(G)其顶点集是G中所有k长路,其中两点相邻当且仅当在G中它们公共部分是k-1长路且它们的并是k+1长路或圈.显然,k=1时,P1(G)就是图G的线图.图G的中间图M(G)的定义为[15]：顶点集是V(G)∪E(G),其中两点x与y相邻当且仅当{x,y)n E(G)≠φ且x,y在G中相邻或关联.本文中,我们把中间图M(G)的概念推广,给出中间Pk-图Mk(G)的概念.图G的中间Pk-图Mk(G)的定义为：顶点集是V(G)∪V,(Pk(G)),边集是E(Pk(G))∪Ek,其中Ek={(v,p):p∈V(Pk(G)),v是p的一个端点.}由上面定义,我们有：k=1时,M1(G)=M(G),k=2时,M2(G)=(V(G)∪V{P2(G),E(P2(G))∪E2).如果图G中含有一个包含所有边的闭迹,称图G是欧拉图.所有顶点度数是偶数的图称为偶图；所有顶点度数是奇数的图称为奇图.本文主要证明了：(1)顶点数|V(G)|≥3的连通图G,若6(G)≥2,则P2(G)连通,M2(G)连通,且入(M2(G))≥2.(2)设G是连通图,如果δ(G)≥3,则λ(M2(G))≥2δ(G).(3)设G是连通图,若G是欧拉图,则M2(G)也是欧拉图.(4)设G和M2(G)都是连通图,若M2(G)是欧拉图,则G是偶图或奇图.

中间P_2-图的边连通性

内容摘要

全文目录

相似论文