幾類有向圖的強直徑和強半徑.pdf

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

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

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

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

5、圖的最小強直徑的一個上界，并成立結(jié)論:6圈添加弦構(gòu)成的弦圖記為H，令G=H(2)，則有sdiam(G)≤6.一般地，將n圈添加弦構(gòu)成的弦圖記為H，令G=H(2)，則有sdiam(G)≤n.
　　 第四章則討論了最小強直徑與最小強半徑相等的特殊圖類.主要結(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(