圖的k次方圖的寬直徑.pdf

1、本文共四章，主要研究了三方面的內(nèi)容：路和樹的k次方圖的寬直徑，并得到圖的k次方圖的寬直徑的界；圈的k次方圖的寬直徑及給出了含圈圖的k次方圖的寬直徑的界；Harary圖的寬直徑．行文結(jié)構(gòu)安排如下： 第一章介紹文章的研究背景，概念以及主要結(jié)論。 設(shè)G=G(V, E)是簡單無向k連通圖，u，v是V(G)中任意兩個(gè)不同的頂點(diǎn)．P<,i>(1≤i≤k)表示連結(jié)u，u的k條內(nèi)部不交的路．|P<,i>|表示路P<,i>的長．記D<,k

2、>(u，v)所有k條內(nèi)部不交的(u，v)路．設(shè)P<,k>(u，v)是u和v間的k條內(nèi)部不交路的集合，即 P<,k>(u，v)={P<,1>，P<,2>，…，P<,k>)，|P<,1>|≤|P<,2>|≤…≤|P<,k>|定義u和v間的k寬距離d<,k>(u，v)： d<,k>(u，v)=min{|P<,k>|:P<,k>(u,v)∈D<,k>(u，v)}并且，G的k寬直徑定義為： d<,k>(G)=max{d<,k>(u，v)：u，v∈

3、V(G)，v≠v}．顯然，d<,k>(G)≥d<,k-1>(G)≥…≥d<,1>(G)=d(G)，其中，d(G)表示G的直徑。 第二章主要討論路和樹的k次方圖的連通度K(G)，及由圖的連通度與直徑相結(jié)合所決定的路和樹寬直徑，即對k≤n-1， d<,k>(P<'k><,n>)=[n/k].并且對k≤d(T)-1, d<,k>(T<'k>)≤[n/k]．進(jìn)而我們得到了一般圖的k次方圖的寬直徑：對k≤d(G)-1，d<,k>(G<'k