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

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

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

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

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

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