兩類圖的最小直徑定向.pdf

1、本文共分兩章，主要研究了圖的最小直徑定向問題． 圖的最小直徑定向問題是在對單行街改造和流言傳播等問題的研究中首次提出的，即如何把一個交通系統(tǒng)的每一條路改為單行路，使得任何兩點均可互相到達且路程最長者達到最?。@兩個問題由于其廣泛的應(yīng)用背景頗受人們關(guān)注，目前仍為研究熱點． 一個無向圖G的一個定向是指一個有向圖D，它是給G的每條邊定一個方向而得到的．如果G的定向D中任何兩個頂點是互相可達的，則稱D是G的一個強定向．一個連通無

2、向圖G中一條邊e稱為G的橋如果G-e不連通．單行街問題可以追溯到Robbins的經(jīng)典論文，文中給出了著名的單行街定理：一個連通的無向圖G有強定向當(dāng)且僅當(dāng)G無橋．當(dāng)一個圖G可以強定向時，它的直徑便為有限的．如何給G定向使得其直徑達到最小，便為圖的最小直徑定向問題． 對于一個無橋的連通無向圖G，令D(G)表示G的強定向圖的集族，對任意D∈D(G)，本文用d(D)(d(G))表示D(G)的直徑．定義d(G)=min{d(D)|D∈D(

3、G))．G(s<,1>，s<,2>，…，s<,n>)(此記號來自[2])為連通無向圖G的頂點擴張圖(n≥3，si≥2，i=1，2，…，n)，Koh和Tay在他們的論文[2]中得到不等式： d(G)≤d(G(s<,1>，s<,2>，…，s<,n>))≤d(G)+2因而所有形如G(s<,1>，s<,2>，…，s<,n>)的圖被分為三類： φ<,i>={G(s<,1>，s<,2>，…，s<,n>)|d(G(s<,1>，s<,2

4、>，…，s<,n>))=d(G)+i)，i=0，1，2同時他們還提出一個猜想[2]：如果無向圖G的直徑大于或等于3，則G的頂點擴張圖G(s<,1>，s<,2>，…，s<,n>)不屬于第三類圖φ<,2>，即G(s<,1>，s<,2>，…，s<,n>)∈φ<,2>，(s<,i>≥2，i=1，2，…，n)．該問題舉出反例和給出證明都很困難． 本文第一章在前人論文的基礎(chǔ)上，得出了樹的2-頂點擴張圖T<'(2)>的最小直徑定向圖的兩個基本