兩類(lèi)圖的最小直徑定向.pdf

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

2、向圖G中一條邊e稱為G的橋如果G-e不連通．單行街問(wèn)題可以追溯到Robbins的經(jīng)典論文，文中給出了著名的單行街定理：一個(gè)連通的無(wú)向圖G有強(qiáng)定向當(dāng)且僅當(dāng)G無(wú)橋．當(dāng)一個(gè)圖G可以強(qiáng)定向時(shí)，它的直徑便為有限的．如何給G定向使得其直徑達(dá)到最小，便為圖的最小直徑定向問(wèn)題． 對(duì)于一個(gè)無(wú)橋的連通無(wú)向圖G，令D(G)表示G的強(qiáng)定向圖的集族，對(duì)任意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>)(此記號(hào)來(lái)自[2])為連通無(wú)向圖G的頂點(diǎn)擴(kuò)張圖(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>)的圖被分為三類(lèi)： φ<,i>={G(s<,1>，s<,2>，…，s<,n>)|d(G(s<,1>，s<,2

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