若干特殊圖的最小強(qiáng)直徑定向.pdf

1、無向圖G中兩點(diǎn)u，v的距離是G中最短的(u，v)路的長(zhǎng).無向圖G的直徑是指G中任意兩個(gè)頂點(diǎn)之間的最大距離.有向圖中直徑定義類似.有向圖D中點(diǎn)u，v之間的強(qiáng)距離是包含u，v的D的強(qiáng)連通子圖的最小弧數(shù)，有向圖D的強(qiáng)直徑指D中任意兩點(diǎn)強(qiáng)距離的最大者.圖G的定向是對(duì)G的每條邊指定一個(gè)方向，這樣由G得到的有向圖D叫做G的定向.如果G的定向D中任意兩點(diǎn)之間可以相互到達(dá)，則稱D為G的強(qiáng)定向.在G的所有可能的定向中，強(qiáng)直徑最小的定向稱為G的最小強(qiáng)直徑定

2、向，其最小強(qiáng)直徑記為sdiam(G).
　　本文分為三章，主要內(nèi)容如下:
　　第一章的第一部分介紹了圖的一些基本概念和術(shù)語.第二部分給出了強(qiáng)直徑和最小強(qiáng)直徑定向的一些重要結(jié)果.
　　第二章的第一部分主要討論了最小強(qiáng)直徑定向，得到了以下結(jié)果:
　　定理設(shè)H是n（n≥3）階樹，則sdiam(H(2)={2dian(H)+2，diam(H)≤22diam(H)，diam(H)≥3。
　　另外，對(duì)一般的n(n≥3)

3、階連通無向圖G，我們還得到了下面的關(guān)系式:2diam(G)≤sdiam(G(2)≤2diam(G)+2.
　　第二章的第二部分討論了圈的最小強(qiáng)直徑定向，得到了以下結(jié)果:
　　定理當(dāng)n是偶數(shù)時(shí)，sdiam(C(2)n)=2diam(Cn);
　　當(dāng)n是奇數(shù)時(shí)，2diam(Cn)≤sdiam(C(2)n)≤2diam(Cn)+1.
　　第二章的第三部分討論了單圈圖的最小強(qiáng)直徑定向，并有下面的結(jié)論:
　　定理若G

4、是n階單圈圖，diam(G)≥3，則sdiam(G(2)=2diam(G).
　　第三章的第一部分討論了路與路的乘積的最小強(qiáng)直徑定向，得到了以下結(jié)果:
　　定理記Pk是長(zhǎng)度為k-1的路，令G=Pm×Pn(m≥2，n≥2)則sdiam(G)=2diam(G).
　　并且還證明了，對(duì)無向圖G，若ρ(G)=0，有sdiam(G)=2diam(G).
　　第二部分討論了路與路的強(qiáng)乘積的最小強(qiáng)直徑定向，得到了以下結(jié)果: