幾類有向圖的強(qiáng)直徑和強(qiáng)半徑.pdf

1、無(wú)向圖G中兩點(diǎn)u，v之間的距離是G中最短的(u，v)路的長(zhǎng).無(wú)向圖G的直徑是指G中任意兩個(gè)頂點(diǎn)之間距離的最大者.類似地，有向圖D中點(diǎn)u到點(diǎn)v的距離指u到v的最短路的長(zhǎng)度.另外，Chartrand et al.定義了有向圖D中兩個(gè)點(diǎn)u，v之間的強(qiáng)距離sd(u，v)是包含u，v的D的強(qiáng)連通子圖的最小弧數(shù).有向圖D中點(diǎn)v的強(qiáng)偏心距se(v)定義為v到V(D)中任意一點(diǎn)的強(qiáng)距離的最大值.有向圖D的強(qiáng)直徑指D中任意一個(gè)點(diǎn)強(qiáng)偏心距的最大值，類似地，

2、有向圖D的強(qiáng)半徑指D中任意一個(gè)點(diǎn)強(qiáng)偏心距的最小值.給定一個(gè)無(wú)向圖G，將G的每條邊{x，y}用弧xy或yx替代后得到的有向圖稱為G的定向圖.若連通圖G在定向后是強(qiáng)連通的，則稱該定向?yàn)镚的強(qiáng)定向.使得G的所有定向圖中強(qiáng)直徑最大的定向稱為G的最大強(qiáng)直徑定向，其最大強(qiáng)直徑記為SDIAM(G).在G的所有可能的強(qiáng)定向中，強(qiáng)直徑最小的定向稱為G的最小強(qiáng)直徑定向，其最小強(qiáng)直徑記為sdiam(G).同理，強(qiáng)半徑的定向類似.對(duì)于無(wú)向圖和有向圖的直徑，許多

3、學(xué)者已經(jīng)研究得出大量結(jié)果.對(duì)于有向圖而言，有關(guān)強(qiáng)直徑和強(qiáng)半徑概念的提出較遲，而且關(guān)于其研究結(jié)果的文獻(xiàn)還很少，因而研究難度也較大.本文主要研究了幾個(gè)特殊有向圖的強(qiáng)直徑及其強(qiáng)半徑的界.
　　 本文分為四章，主要內(nèi)容如下:第一章是預(yù)備知識(shí)，介紹了一些本文中將要用到的圖論方面的基本概念和術(shù)語(yǔ).
　　 第二章簡(jiǎn)要介紹了關(guān)于強(qiáng)直徑和強(qiáng)半徑目前的研究結(jié)果.
　　 第三章的第一部分首先討論了圈的2頂點(diǎn)擴(kuò)張圖的最大強(qiáng)直徑的界，并有

4、如下結(jié)論:設(shè)H是階n≥3的圈，令G=H(2），則有不等式SDIAM≥n+2.特別地研究了奇圈的2頂點(diǎn)擴(kuò)張圖的最小強(qiáng)直徑的定向，得到如下結(jié)論:設(shè)H是階n＞3的圈，其中n為奇數(shù)，令G=H(2），則有結(jié)果sdiam(G)≤n
　　 第二部分首先討論了5圈添加弦后構(gòu)成的弦圖的2頂點(diǎn)擴(kuò)張圖的最小強(qiáng)直徑的一個(gè)上界，并有如下結(jié)論:5圈添加弦構(gòu)成的弦圖記為H，令G=H(2)，則有sdiam(G)≤5.接著討論了6圈添加弦后構(gòu)成的弦圖的2頂點(diǎn)擴(kuò)張

5、圖的最小強(qiáng)直徑的一個(gè)上界，并成立結(jié)論:6圈添加弦構(gòu)成的弦圖記為H，令G=H(2)，則有sdiam(G)≤6.一般地，將n圈添加弦構(gòu)成的弦圖記為H，令G=H(2)，則有sdiam(G)≤n.
　　 第四章則討論了最小強(qiáng)直徑與最小強(qiáng)半徑相等的特殊圖類.主要結(jié)果如下:(1)令G=C(2)3，那么sdiam(G)=srad(G).(2)令G=C(2)4，那么sdiam(G)=srad(G).(3)設(shè)H是4圈添加弦后構(gòu)成的弦圖，令G=H(