有向圖的代數(shù)表示與刻劃.pdf

1、對(duì)圖進(jìn)行代數(shù)性的表示及相關(guān)刻劃是代數(shù)圖論的中心課題之一.本文是在這一課題下針對(duì)有向圖進(jìn)行的研究和探討.事實(shí)上，無(wú)向圖可以可看作是對(duì)稱(chēng)有向圖，即每條無(wú)向邊對(duì)應(yīng)方向互反，端點(diǎn)相同的兩條弧.本文的研究工作主要分兩部分，第一部分通過(guò)對(duì)有向圖的幾種不變量的討論，對(duì)若干有向圖類(lèi)進(jìn)行了研究并給出了一些代數(shù)表示與刻劃.第二部分是對(duì)有向DeBruijn圖這一特殊圖類(lèi)，給出了幾種新的代數(shù)表示與刻劃. 第一章概述了本文研究工作的相關(guān)背景和現(xiàn)狀，以及本

2、文的主要研究結(jié)果.第二章我們用矩陣等式的語(yǔ)言統(tǒng)一表示了有向圖的同態(tài)映射，有向圖覆蓋，因子圖，均勻劃分等概念，并討論了相應(yīng)圖類(lèi)之間的關(guān)系.這一章的工作有獨(dú)立的意義，同時(shí)也是為第三，四章的工作做準(zhǔn)備. 第三至四章我們討論了有向圖覆蓋的特征多項(xiàng)式.Gross和Tucker[80，81]指出，每一個(gè)對(duì)稱(chēng)有向圖(正則)覆蓋都可以通過(guò)對(duì)基圖分配一個(gè)對(duì)稱(chēng)置換(普通)電壓群而得到.這一結(jié)論推廣到一般有向圖也成立.我們突破了已有研究中電壓群只能是

3、有限Abel群的限制，對(duì)電壓群是任意有限群的情況，給出了帶半自由作用有向圖的普通電壓圖表示，和分支指數(shù)為1的分支覆蓋的置換電壓圖表示，并利用有限群表示論的知識(shí)，推導(dǎo)出了這兩類(lèi)圖的特征多項(xiàng)式的分解公式.在以往的研究中提到，群作用有向圖的特征多項(xiàng)式有一個(gè)因式與軌道圖有關(guān)，但沒(méi)有給出其幾何意義，我們明確指出，該因式就是因子圖的特征多項(xiàng)式. Hoffman多項(xiàng)式是對(duì)強(qiáng)連通正則有向圖定義的一個(gè)不變量[92]，我們推廣了這一概念，對(duì)任意非負(fù)

4、不可約矩陣，包括一般的強(qiáng)連通有向圖，定義了Hoffman多項(xiàng)式.我們明確提出了針對(duì)Hoffman多項(xiàng)式來(lái)研究有向圖的判定性和刻劃性?xún)纱箢?lèi)問(wèn)題，并就此展開(kāi)了具體的研究.這一部分內(nèi)容集中在第五章.我們指出了Hoffman多項(xiàng)式與矩陣方程之間的關(guān)系，討論了某些特殊圖類(lèi)對(duì)應(yīng)的矩陣方程；并計(jì)算了有向圖張量積的Hoffman多項(xiàng)式；探討了兩個(gè)初等等價(jià)矩陣的Hoffman多項(xiàng)式之間的關(guān)系，包括對(duì)有向線圖及其基圖，有向合并圖和有向分裂圖的相關(guān)表示和刻劃

5、；還針對(duì)一些特殊的多項(xiàng)式，研究了這些多項(xiàng)式成為有向圖的Hoffman多項(xiàng)式的條件. DeBruijn圖[28]是有著豐富研究及應(yīng)用背景的圖類(lèi)，在組合學(xué)，計(jì)算機(jī)網(wǎng)絡(luò)，光纖通訊，自動(dòng)機(jī)，分形學(xué)，量子計(jì)算等許多研究領(lǐng)域都受到關(guān)注.本文第六章從代數(shù)結(jié)構(gòu)出發(fā)定義了一類(lèi)陪集圖，由此給出了有向DeBruijn圖的一個(gè)代數(shù)表示及相應(yīng)刻劃，該刻劃證實(shí)并推廣了Fiduccia和Jacobson[64]提出的一個(gè)猜想.我們?cè)诘谄哒掠懻摿擞邢駾eBru