有向圖的代數表示與刻劃.pdf

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

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

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

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

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