摘要 摘要 圖g 的l a p l a c i a n 矩陣l ( g ) 是研究圖的性質(zhì)的一個重要工具人們傳統(tǒng)上 用l ( g ) 的特征值來研究圖論，得到很多很好的結(jié)論近二十年來，人們發(fā)現(xiàn)l ( g ) 的s m i t h 標準型和特征值一樣，同為圖的同構精細不變量，自然也是研究圖論 的好工具作者最早接觸到的臨界群概念，是源自g o d s i l 和r o y l e 的著作g t m 2 0 7 國際著名數(shù)學家b i g g s 在1 9 9 9 年的時候證明了圖的臨界群能夠被l ( g ) 的 s m i t h 標準型所刻劃本文研究了兩類c a r t e s i a n 乘積圖g 和a c _ 的 l a p l a c i a n 矩陣，得到了它們的s m i t h 標準型，給出了這兩類圖的臨界詳細群結(jié)構 和生成樹數(shù)目對于一般化的圖，我們給出了其s m i t h 標準型的前三個不變因子 的精確上界 下面的是本篇論文得到的主要結(jié)果，其中的參數(shù)在正文對應部分都有詳細的 介紹 若禮= 2 s + l ，則g ( m ，禮3 ) 的臨界群為 五n ，如) o 磊。o 面。o o 磊巳。乙of z m h so o k ，o 乙， - _ _ - _ - _ o 、j _ - _ _ _ _ ，1 - - - _ _ _ - _ _ _ j - - - _ _ - _ - o ， 其中一= 而h 8 ( 玨，) ，妒= 麗n m h 萬s 若禮= 2 s ，則g ( m ，n 3 ) 的臨界群為 互2 n ) o 么。乙m ，2 ) 釷。o o 互m ，2 ) 玨。o 磊。乙o & o o 么o 么， 、_ - - l _ l l - _ i 、j _ - _ _ l l l _ _ i _ - ，l - _ _ l 、，l _ - o r m - 3 m 一3 其中 廣讓s 【n ，缸8 ，4 丁8 j 2 芒r ， f u 。2 l 1 叼= 坐菘n 糍4 t s 掣) ， 【，亂s ， p = 墜甕辮，i 佗，一4 j l m ，z ) x = 糌， ，n m ( m + 4 ) u 5，：= ( m n ，( m + 4 ) u ，2 n ) 摘要 由此得到g 的支撐樹的數(shù)口為 熹( ( 翌塵生蘭譬) n + ( ! _ 二生雩) n 一2 ) m 一1 若n = 2 s + 1 ，則a c km 3 ) 的臨界群為 級撕，k ) o s ，a ) 。z 錯。級。z n 嘴淵。z 踽。z 兩 l，一， jl n o 兒 j ， oj、 5 ， 5 ，肌a 4 ， 0 ， 若孔= 2 s 且s 為奇數(shù)，則q g 3 ) 的臨界群為 z ( 舭，1 ) 。z ( ，i ) 。z 獬 z e e 。j。z 黜i s )。z 耥。z 融 j t，o ，l j te 兒e 8 c 0 j j5 e s ，4 j d 0 4 j ， 若n = 2 s 且s 為偶數(shù)，則a g ( 佗3 ) 的臨界群為 缸舭， ) 。反e ，厶) 。z 等高將儼。磊e 。z 號黯e 最s ) 鼎。z 舶。z t s e s 當s ，8 ，jj to ，0 jo a ，j ， 5 j 4 ，o ， 由此得到圖僅g 的支撐樹的數(shù)目為 囂( ( 銹+ 1 ) n 一( 鋸一1 ) - - 1 ) 4 。( ( 詎+ 1 ) n 一( 钷一1 ) - - 1 ) 2 ，若n 為奇數(shù)； l - 南( ( 佰+ 1 ) n 一( 鏞一1 ) n ) 4 ( ( 以+ 1 ) n 一( 鉅一1 ) n ) 2 ， 若禮為偶數(shù) 從而證明了當禮 3 時有以下三角函數(shù)恒等式成立 t l 一1 兀i4 j = l 菇1 【( 2 2c o s 號 4 ( 此外，對仃5 階的簡單連通非完全圖g ，還得到了它的第三位不變因子的 定位：8 3 ( g ) 并且8 3 ( g ) = n 當且僅當g = 一e ，其中e 的任意一條邊； 8 3 ( g ) = 禮一1 當且僅當g = 口一l ，其中7 t 5 且g 由完全圖一l 連接一個 垂點2 ，所得；s a ( g ) = 扎一2 當且僅當佗= 5 且g = 熄一2 e ，其由凰刪除兩條不相 鄰的邊所得，或g = 磁一q ，其由蠔刪除長為4 的圈的邊所得；8 3 ( g ) = 禮一3 當 且僅當g 為下述六種圖之一：鮑，3 ，蠔一g ，甄一傷，硒一2 島，凰，3 及坼一凰，3 關鍵詞：l a p l a c i a n 矩陣，s m i t h 標準型，臨界群，不變因子 n 一以一 ， ) 以型n+ 2 一 l 一，一曲 6 g 2 一 一、，2 旦仃一 打i 一 劫 融 面 a b s t r a c t a bs t r a c t t h e l a p l a c i a nm a t r i xi sap o w e r f u lt o o li ng r a p ht h e o r y t r a d i t i o n a l l y ，t h ep e o p l e u s et h ee i g e n v a l u e so ft h el a p l a c i a nm a t r i xt od e s c r i b et h ep r o p e r t i e so fg r a p h sa n d g e tal o to fv e r yn i c er e s u l t s i nt h el a s tt w e n t yy e a r s ，t h es m i t hn o r m a lf o r mo fl ( g ) i sf o u n dt ob et h ef i n ei n v a r i a n to fi s o m o r p h i s mo ng r a p h sa sw e l la st h el a p l a c i a n e i g e n v a l u e s ，s oi ti sm e a n i n g f u lt op a yo u ra t t e n t i o nt ot h es m i t hn o r m a lf o r mo fl ( g ) w ek n o wt h ec r i t i c a lg r o u pf r o mg t m 2 0 7 ，w h i l et h ef a m o u sm a t h e m a t i c i a nn b i g g s s t a t e dt h a tt h ec r i t i c a lg r o u po fag r a p hi sd e p e n do ni t ss m i t hn o r m a lf o r mi n 1 9 9 9 i nt h i st h e s i sw ed e s c r i b et h es m i t hn o r m a lf o r m so ft w ok i n d so fc a r t e s i a np r o d u c t g r a p h s ：ga n dq g t h e nw eg e tt h e i rc r i t i c a lg r o u p sa n dt h es p a n n i n gt r e e n u m b e r s i nt h el a s tc h a p t e ro ft h i st h e s i sw ew i l ls h o wt h es h a r pu p p e rb o u n d so ft h e f i r s tt h r e ei n v a r i a n tf a c t o r so ft h es m i t hn o r m a lf o r mo fg r a p hg t h ef o l l o w i n g sa r e t h em a i nr e s u l t sw h e r et h ep a r a m e t e r sw i l lb ee x p l a i n e di nt h e c o r r e s p o n d i n gp a r to ft h em a i nt e x t i f 仃= 2 s + 1 ，t h e nt h ec r i t i c a lg r o u po fk r m g ( m ，n 3 ) - i s 反m 9 。) 。磊。迢：旦0 里圣：，。乙。冬生旦0 里圣。乙， t r 卜一2 m - 3 w h e r e 7 = 瓦h 面8 ( n ，九。) ，壚= 瓦n m 面h s i f n = 2 s ，t h e nt h ec r i t i c a l g r o u po f k 擊g ( m ，n 3 ) i s z ( u 。，2 n ) o 反oz ( m ，2 ) u 。o oz ( 。，2 ) u 。o 乙。乙。么o o 反。么， 、o - - _ _ - _ _ l l _ _ - _ o 、j _ - i l _ l - l - l _ 一、- _ l _ _ l o 、j _ _ _ _ _ _ - 一 m 一3m 一3 u l a b s t r a c t w h e r e t h e nt h en u m b e ro fs p a n n i n gt r e e so fk mxgi s 景( ( ! 三三乒) n + ( 翌生竺二譬) n 一2 ) m 一1 i f n = 2 s + 1 ，t h e n t h ec r i t i c a lg r o u p o f a c ( n 3 ) i s 互撕k ) 9 缸k ) 。z 錯。乙a 。z 淵。z 蹁。z 贏f l t , a 8 l n ，k a ， jt n ，k 5 兒一， jj ， jl n 0 一j j i f n = 2 sw i t hso d d ，t h e nt h ec r i t i c a lg r o u po fq 僅( t , 3 ) i s 瓦，| ) 。，| ) 。z 黜。五一。z 淵( e 8。z 黼。z 赫t $ c ，oj，ic oj，j0 0 ，ajl j 0 to ，5 ，e ，j i f 竹= 2 sw i t hse v e n ，t h e nt h ec r i t i c a lg r o u po fa g m 3 ) i s 厶) 。，厶) 。z 黼彤f l 、厶7 6 e 。z 黜。z 熬。z 蒜群0 ，8 0 ，jjo 8 5 兒o o t ，j )c 5 ，j ，t o o 8 ，s - 8 0 ，jj t h e nt h en u m b e ro fs p a n n i n gf l e e so fq gi s 殺( ( 鋸+ 1 ) 一( 鋸一1 ) 州) 4 ( ( 以+ 1 ) - ( v 互- i ) n - 1 ) 2 ， 南( ( 銹+ 1 ) n 一( 銹一1 ) n ) 4 ( ( 以+ 1 ) n 一( 以一1 ) n ) 2 ， s o ，i fn 3 ，t h ef o l l o w i n ge q u a t i o nh o l d s n一-l(h 4 o 孚) 2 ( 6 地o s 等) = 去 ( 2 + 娟) 鷥一( 2 一怕) 號 4 ( 1 + 以) n 一( 以一1 ) n 2 i f ni s o d d ； i f 仃i s e v e n a b s t r a c l f u r t h e rm o r e ，f o ras i m p l ec o n n e c t e dg r a p hg 玩w i t ho r d e r7 , 5 ，t h et h i r d i n v a r i a n tf a c t o r8 3i sd e s c r i b e da sf o l l o w ：s 3 ( g ) 禮a n d8 3 ( g ) = 佗i fa n do n l yi f g = 一e ，w h e r eei sa ne d g eo f ；s 3 ( c ) = 死一1i fa n do n l yi fg = 移。一1 ； s 3 ( g ) = 一2i f a n do n l yi f n = 5a n dg = k 5 2 eo rg = 蠔一甌；s 3 ( c ) = n 一3 i f a n do n l yi f gi so n eo f t h ef o l l o w i n gg r a p h s ：鮑蠔一傷，甄一g ，瑪一2 6 3 ， k z 3a n dk 7 一k 3 3 k e y w o r d s ：l a p l a c i a nm a t r i x ，s m i t hn o r m a lf o r m ，c r i t i c a lg r o u p ，i n v a r i a n tf a c t o r v 中國科學技術大學學位論文原創(chuàng)性和授權使用聲明 本人聲明所呈交的學位論文，是本人在導師指導下進行研究工 作所取得的成果。除已特別加以標注和致謝的地方外，論義中不包 含任何他人已經(jīng)發(fā)表或撰寫過的研究成果。與我一同工作的同志 對本研究所做的貢獻均已在論文中作了明確的說明。 本人授權中國科學技術大學擁有學位論文的部分使用權，即： 學校有權按有關規(guī)定向國家有關部門或機構送交論文的復印件和 電子版，允許論文被查閱和借閱，可以將學位論文編入有關數(shù)據(jù)庫 進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編學位 論文。 保密的學位論文在解密后也遵守此規(guī)定。 州作者虢 凇f 6 年石月) e 1 第一章引言 第一章引言弟一早ji 百 1 1 圖的基本概念 圖是一種二元的拓撲結(jié)構，由兩個部分構成：頂點和邊頂點集合( v e r t e xs e t ) 是圖的基礎部分，記為y ，而邊集( e d g es e t ) 表示了頂點與頂點之間的關系，記為 e 頂點集合與邊集共同構成一個圖 對某個具體的圖g ，e ( g ) 可以看做是建立在v ( g ) v ( g ) 上的個映 射：e e ( g ) = ( z ，! ，) ，這里z ，秒y ( g ) 稱頂點茁，y 為邊e 的兩個端點( e n d p o i n t ) ，邊e 和頂點z ，可是相關聯(lián)的( i n c i d e n t ) ，而稱z 和y 是相鄰或鄰接的 ( a d j a c e n t ) 若這樣的頂點對( z ，y ) 是無序的，即e = ( z ，y ) = ( ! ，z ) ，則稱e 是無向 的；反之，若這樣的頂點對( x ，y ) 是有序的，即e = ( z ，y ) ( y ，z ) ，則稱e 是有向 的 若e ( g ) 中所有的邊e 都是無向的，則稱圖g 為無向圖( u n d i r e c t e dg r a p h ) ； 對應的，若e ( g ) 中所有的邊e 都是有向的，則稱圖g 為有向圖( d i r e c t e d g r a p h ) 一個圖可能既包含有向邊，又包含無向邊本文中若無特別說明，均討論無向圖的 情形 若某條邊的兩個端點相同，即e = ( z ，z ) ，那么邊e 稱為環(huán)( 1 0 0 p ) 如果兩 條或者更多的邊具有相同的兩個端點，即e 1 = e 2 = = e k = ( x ，秒) ，則稱 e l ，e 2 ，e k 為一組重邊( m u l t i e d g e s ) 或者平行邊( p a r a l l e le d g e s ) 一個圖中如 果沒有環(huán)和重邊，我們稱它為簡單圖( s i m p l eg r a p h ) 本文中若無特別說明，圖g 均是指簡單圖 我們來看一些常見的圖設v = z 1 ，z 2 ，z n ) 為圖的頂點集把任意兩 點都連起來就得到完全圖( c o m p l e t eg r a p h ) ，用記號k 表示，它的邊集是( z i q ： 1 i u z 1 ) 如果無向圖中任意兩點之間都至少存在一條路相連，則稱這樣的圖為連通圖 ( c o n n e c t e dg r a p h ) 1 第一章引言 1 2圖的運算 圖與圖之間有多種乘積，我們只給出本文所用到的笛卡爾( c a r t e s i a n ) 乘積的 定義 兩個圖g l 和g 2 的笛卡爾乘積用g 1 g 2 表示，定義如下： 設g 1 = ( ，e 1 ) ，g 2 = ( v 2 ，島) 是兩個簡甲圖，他們的笛卡爾乘積圖為 g = ( ve ) ，其中v = ( 笛卡爾積) ，對心l ，u 2 ) 。 t ，0 2 ) v ，( u 1 ，u 2 ) 和( u l ，刀2 ) 在g l g 2 巾相鄰當且儀當讓1 = t ，1 ，( t 正2 ，飽) e 2 ，或者缸2 = 耽， ( u l ， 1 ) e 1 例如下圖： 9 i t l g 1 l 上l 亂2 ( 亂l ，z 1 2 )( u l ，v 2 )( u l ， 0 2 ) 也 口 ? 3 2 ( t ，l ，讓2 )( ? 3 1 ，2 3 2 )( u l ，? - 1 3 2 ) g 1 g 2 圖1 2 笛卡爾乘積圖 1 3 與圖相關的矩陣 下面我們引入幾個與圖關系密切的矩陣在無向圖g = ( e ) 中，頂 點集記為v = v l ， 0 2 ， ，邊集為e = 2 m n ，則游戲會無限進行下去 ( 2 ) 若msn 2 m 一死，游戲可能無限進行下去或者在有限步之后停下。 ( 3 ) 若n 2 m 一禮，根據(jù)抽屜原理，在任意狀態(tài)下，一定會存在一個頂點， 它上面的籌碼數(shù)不小于它的頂點度，此時游戲可以進行下去狀態(tài)是任意的，所以 游戲會無限進行同樣的，當n 2 m n 時，如果某個狀態(tài)下每個頂點上的籌碼 數(shù)量都小于等于d ( u ) 一1 ，則每個頂點都不能被發(fā)射，即游戲到此為止，一定是有 限步 要完成( 2 ) 的驗證，還需要我們給出當n m 時，游戲可以無限進行下去的 情形顯然的，只需要建立n = m 時( 2 ) 成立的情況即可： 我們將圖g 的所有佗個頂點釘l ， 0 2 ，都給個標號，分別為1 ，2 ，n 兩 個頂點z 和之間若存在邊e ，則規(guī)定e 的方向為從小標號端點指向大標號端點 在此定向之下，規(guī)定頂點口上的初始籌碼數(shù)目為以u 作為小標號端點的邊的數(shù) 目。由于每一條邊都有且只有一個小標號端點，所有此時圖g 上的籌碼總數(shù)和邊 的數(shù)目相同，為m 考慮標號為1 的頂點t ，1 ，它的所有鄰邊都以它為小標號端點， 所以它上邊的籌碼數(shù)目恰好等于它的度數(shù)，也就是說，此狀態(tài)下頂點u l 是可以發(fā) 射的，即游戲可以進行下去接下去要考慮u l 發(fā)射之后的籌碼分布狀態(tài)，我們發(fā) 現(xiàn)，它恰好是這樣的一個狀態(tài)：將圖g 的所有n 個頂點鈔l ，口2 ，都給個標 號，分別為t t + 1 ，2 ，禮，邊的定向和籌碼分布的規(guī)則和之前相同此時來看 2 ，類似于之前對 1 的討論，它也是可以發(fā)射的事實上，某個頂點u 發(fā)射之后的 狀態(tài)都恰好是將它的標號增加銘，其他頂點標號不變所得的分布狀態(tài)顯然，以此 類推，頂點標號有無限種，所以游戲可以無限進行下去 而當 m 時，發(fā)射過程只能在進行有限步后停下 6 第二章圖的臨界群和弧r i r e 多項式 這里涉及到無圈定向的概念般的說，將一個無向圖的每條邊都規(guī)定一個 方向，若由此得到的有向圖不包含有向圈，則此規(guī)定為無圖定向( 參見【1 4 1 ) 本章的 后面我們還會提到這個概念 對于可以無限發(fā)射下去的游戲狀態(tài)，任意時刻都存在可以發(fā)射的頂點，并且 在同一時刻可以發(fā)射的頂點數(shù)可能不止一個，那么自l 果我們選擇的發(fā)射順序不 同，是否會對游戲的進行造成影響? 例如同時存在兩個可發(fā)射的頂點時，先發(fā)射 其中個可以讓游戲無限進行下去，而如果選擇先發(fā)射另外一個的話會不會讓游 戲在某一個狀態(tài)就停下來了? b j o r n e r 在文章1 3 】中給出了一些定理來來闡述這些 可能性，同樣的在代數(shù)圖論的教材中也能找到答案 定理2 1 2 【1 3 】3 2 3g 是連通圖，8 是某個給定的初始狀態(tài)那么從s 開始的任 意發(fā)射序列，或者都是無限的，或者都終止于某個相同的狀態(tài) 此定理說明了發(fā)射的順序是不影響的游戲進行的最終結(jié)果的在有多種選擇 的情況下，任意選擇發(fā)射的順序都不會對游戲結(jié)果造成影響 在b i g g s 的文章【9 】中，他將圖進行標號，對于一個發(fā)射序列，我們可以用一 個發(fā)射向量來表示其每一個頂點發(fā)射的次數(shù)，向量的第i 個分量就表示頂點訌在 整個過程中發(fā)射的次數(shù)對于兩個發(fā)射向量z 和y ，我們定義向量運算zvy 如下 ( v 影) 罄= ? 玨8 z z 缸，玩) 對應的，如果和1 - 是兩個發(fā)射序列，我們定義序列運算仃丁如下： 對每個頂點釷，如果似在。中發(fā)射了i 次，就從7 中去掉u 的前i 次發(fā)射( 如果不 到i 次就全部去掉) ，余下的按順序保留在盯后而，組成新的發(fā)射序列 我們會發(fā)現(xiàn)，原來的兩個發(fā)射序列在此運算下得到的新序列也是一個發(fā)射序 列，即如下定理 定理2 1 3i 9 】g 是一個連通圖，盯和7 - 是從同一個初始態(tài)8 開始的兩個發(fā)射 序列，其發(fā)射向量分別為z 和可，則在7 - 之后接上序列o r 丁也是從8 開始的一個 發(fā)射序列，并且其發(fā)射向量為zv 影。 這個定理用具體的算法說明了對于同一個初始態(tài)，選擇不同的發(fā)射順序并不 能改變游戲的最終狀態(tài)設丁是一個從8 開始的只能進行有限步的發(fā)射序列，口 是從8 開始的另一個發(fā)射序列，由上述定理可知，盯丁只能是仃，因此盯也是有限 的現(xiàn)在假設o r 終止于另外一個狀態(tài)，由于7 和下盯都是o r ，所以口和彳具有 相同的發(fā)射向量游戲的最終狀態(tài)只由初始態(tài)以及發(fā)射向量決定，從而這兩個發(fā) 射序列必然終止于相同的狀態(tài) 7 第二章罔的臨界群和t i l l 多項式 在一個無限發(fā)射的游戲中，顯然會有些頂點發(fā)射了無數(shù)次，但是否會存在 某些頂點，只發(fā)射了有限次，從某個狀態(tài)開始就再也不發(fā)射了，或者從始至終都沒 有發(fā)射過呢? 下述的定理給出了問題的結(jié)論 定理2 1 4 【1 3 】3 2 1 對于一個能夠無限地進行下去的游戲，它的每一個頂點都 會被發(fā)射無數(shù)次 這個性質(zhì)告訴我們，在一個無限發(fā)射的過程中，任何一個頂點都會不停地發(fā) 射反之，若存在某個頂點從某個狀態(tài)開始不再發(fā)射，則發(fā)射必然會在有限步之后 停下來 若一個游戲在有限步之后停。卜了，我們可以研究它從開始至停下來發(fā)射的總 次數(shù)，文章f 1 3 】3 2 3 中給出了以下估計 定理2 1 5g 是連通圖，有釓個頂點，e 條邊，其直徑為d ，則籌碼在g 上的 發(fā)射總次數(shù)不超過2 n e d 這個定理給出了頂點的發(fā)射總次數(shù)的一個上界對應的，如果引入大家熟悉 的l a p l a c i a n 矩陣的特征值，還可以得到另一個上界 定理2 1 6 【1 3 l3 2 5g 是連通圖，有禮個頂點，g 上共有個籌碼若游戲在有 限步之后停下，則發(fā)射總次數(shù)不大于以紹入2 ，其中a 2 是l a p l a c i a n 矩陣z ( o ) 的第二小的特征值，即最小正特征值( 代數(shù)連通度) 定義2 1 對于狀態(tài)8 ，如果存在一個發(fā)射序列，使得s 在經(jīng)過這個序列的發(fā)射 后，又重新回到了狀態(tài)8 ，我們就稱8 是一個循環(huán)態(tài) 顯然，任意一個初始態(tài)在經(jīng)過一個序列發(fā)射之后如果變成了循環(huán)態(tài)，那么它 將一直循環(huán)下去，這時游戲是無限的相反的，如果發(fā)射在有限步之后停下了，那 在整個發(fā)射過程中都不會有循環(huán)態(tài)出現(xiàn)也就是說給定了初始態(tài)，游戲能無限進 行下去當且僅當在某次發(fā)射之后游戲狀態(tài)變成了循環(huán)態(tài) 現(xiàn)在我們引入個新的概念發(fā)散態(tài)( d i f f u s es t a t e ) 定義2 2 若在某個狀態(tài)下，若圖g 的任何一個點導出子圖x 都至少包含一 個點u ，它上面的籌碼數(shù)不少于。在子圖x 中的度數(shù)，則稱此狀態(tài)為發(fā)散態(tài) 8 事實上，發(fā)散態(tài)和循環(huán)態(tài)是等價的 定理2 1 7 一個狀態(tài)是循環(huán)態(tài)當且僅當它是發(fā)散態(tài) 第二章圖的l 晦界群軺n 玎r e 多項式 證明：我們只需要證明以下兩利- 情況： 設s 是一個循環(huán)態(tài)，仃是一個發(fā)射序列，s 經(jīng)過序列仃發(fā)射后又回到s x 是g 的任意一個點導出子圖考慮x 中最先結(jié)束發(fā)射的頂點v ，我們會發(fā)現(xiàn)口在 x 中的鄰點在 的結(jié)束發(fā)射之后都至少還會再發(fā)射一次因此回到循環(huán)態(tài)s 時， 鈔上籌碼的個數(shù)一定不小于它在x 中的度數(shù)即8 是發(fā)散態(tài) 反過來，假設s 是發(fā)散態(tài)由于g 可以視為它本身的一個導出予圖，因此 上面至少有一個點是可以發(fā)射的現(xiàn)假設有某些點已經(jīng)發(fā)射過一次，考慮剩下的 那些點的導出子圖，記為x 由發(fā)散態(tài)的定義，x 中至少有一個點口，它原本的籌 碼數(shù)不小于u 在x 中的度數(shù)；而由假設，它的那些不屬于x 的鄰點都已經(jīng)發(fā)射 過一次，所以此時 上的籌碼數(shù)一定不小于它在g 中的度數(shù)，所以此時v 是可以 發(fā)射的由歸納法可知，發(fā)射過程可以一直繼續(xù)下去，并且容易發(fā)現(xiàn)發(fā)射過程中每 個點都只發(fā)射一次s 經(jīng)歷一個循環(huán)后會回到初始狀態(tài)，因此s 是循環(huán)態(tài)口 在上述定理的證明過程中，我們還可以得到下面的結(jié)論 定理2 1 8 圖g 是連通圖，有仇條邊，則g 的無圈定向和g 上的籌碼總數(shù)為 仇的發(fā)散態(tài)之間存在一一對應 i e n ：設“，是圖g 的一個無圈定向，誘導定義5 = s ( 叫) = ( 8 1 ，8 2 ，s n ) 其中，對任意的1 i n ，8 t 表示頂點地在無圈定向叫下的出度這樣，8 就是圖 g 的一個狀態(tài)我們只需要證明，是無圈定向當且僅當s 是發(fā)散態(tài) ( 1 ) 若u 是無圈定向 考慮g 的某個點導出子圖x ，g 上的無圈定向u 限定在x 上也是x 的一 個無圈定向i x 那么在x 上至少存在一個頂點，它限制在x 上的出度恰好等于 它限制在x 上的度，所以這個點上的籌碼數(shù)等于這個點限制在x 上的度，由定 義s 是發(fā)散態(tài) ( 2 ) 若8 是有m 個籌碼的發(fā)散態(tài) 考慮從8 開始發(fā)射到下一個sm 現(xiàn)之間的發(fā)射情況此過程中每個點恰好發(fā) 射了一次，發(fā)射序列構成了頂點集的一個輪換按照所有n 個頂點在輪換中出現(xiàn) 的先后順序v 1 ，v 2 ，給它們作標號，分別記為1 ，2 ，禮兩個頂點x 和 y 之間若存在邊e ，則規(guī)定e 的方向為從小標號端點指向大標號端點此定向叫是 一個無圈定向，而由定理2 1 1 的證明可知，此時s ) 恰好是個循環(huán)態(tài)，也即是發(fā) 散態(tài)口 若在某個狀態(tài)下，有且只有頂點q 是可發(fā)射的，則稱該狀態(tài)為q 一穩(wěn)定的這 時若q 不發(fā)射，其他頂點就不能發(fā)射若一個狀態(tài)既是q 一穩(wěn)定的，又是循環(huán)態(tài)，則 稱它為g 一臨界態(tài) 9 第二章圖的臨界群和1 弋r i t e 多項式 口一臨界態(tài)是循環(huán)態(tài)，由定理2 1 1 可知，圖g 上的籌碼總數(shù)不少于圖的邊數(shù) 而當籌碼總數(shù)恰好為邊數(shù)時，我們有以下結(jié)論 定理2 1 9 圖g 是有m 條邊的連通圖，則在m 個籌碼的口一臨界態(tài)與圖g 的以q 為唯一發(fā)射源的無圈定向之間存在一個一一對應 定理2 1 1 0 圖g 是有9 7 z 條邊的連通圖，令t 是一個口一臨界態(tài)，那么存在一 個有m 個籌碼的q - i f $ 界態(tài)8 ，使得對任意頂點 上面的籌碼數(shù)，都有8 t 移 由此我們可以將那些有m 個籌碼的口一臨界態(tài)看作是最小臨界態(tài)，其余那些 籌碼數(shù)大于m 的臨界態(tài)，可以由某個最小臨界態(tài)在某些頂點上加上一些籌碼得 到 注釋2 1 1 1 在口一臨界態(tài)中，g 點上的籌碼是沒有限制的，甚至可能是無窮大， 而其它點”上籌碼的個數(shù)都不超過d ( u ) 一1 ，且不小于零因此，整個圖上的籌碼 數(shù)是沒有上限的。 2 2 臨界群 在b i g g s 的文章1 9 】中，將籌碼發(fā)射游戲的規(guī)則做了改進：在圖中取定一個特 殊的頂點g ，在發(fā)射的過程中，q 發(fā)射當且僅當其它的頂點都不能發(fā)射我們把此 規(guī)則下的籌碼發(fā)射游戲稱為美元游戲( d o l l a rg a m e ) 如果把圖中除q 以外的頂點 看做是獨立的經(jīng)濟體，每次發(fā)射過程看成是它們之間的資金流通，那么g 則扮演 政府的角色；也就是說，在資金流通順暢的情況下，政府不做動作，如果資金流通 中斷，也即其它頂點都不能再發(fā)射的時候，“政府”q 就必須發(fā)射以帶動其它頂點 發(fā)射 美元游戲以及籌碼發(fā)射游戲都與圖的l a p l a c i a n 矩陣都有著緊密的聯(lián)系回 顧之前的定義，令8 是美元游戲中的一個狀態(tài)，它表示在某一時刻圖中頂點上的 籌碼數(shù)目，s ( u ) 就表示頂點t ，上的籌碼數(shù)目事實上，我們可以將8 看作一個向 量，其維數(shù)等于圖的頂點數(shù)，每個分量表示對應頂點上的籌碼數(shù)目令s 是個 非空有限的發(fā)射序列( 當然同一個頂點可以發(fā)射多次) ，在這個序列的發(fā)射過程中， 頂點v 發(fā)射的次數(shù)記為z ( u ) 8 經(jīng)過s 這個發(fā)射序列后變?yōu)? 7 ，8 7 可以表示如下 s 7 ( 口) = s ( u ) 一z ( u ) d ( u ) + 。( 叫) ( ，伽) 叫釘 每次t ，發(fā)射都會失去d ( 釘) 個籌碼，而其它的頂點叫u 發(fā)射時，穢都會得到 l ，( u ，幻) 個籌碼，其中( u ，叫) 是u 與叫2 _ 1 ；- 1 的連邊數(shù) 1 0 第二章圖的臨界群和n 1 1 r r e 多項式 我們可以用圖的l a p l a c i a n 矩陣l ( o ) 將上面的兩個狀態(tài)聯(lián)系起來 其中 = 8 一l z ， ，rd ( u ) ， b u y2 氣 【一工，( 牡， ) ， 若u = u ， 若亂u ， 注釋2 2 1 在美元游戲中，我們不關心頂點g 上的籌碼數(shù)，因為不論它上面 有幾個籌碼，只要當其它頂點都不能發(fā)射的時候，q 就必須要發(fā)射因此q 點上的 籌碼數(shù)，根據(jù)討論的問題不同，會有不同的設定一般情況下，我們默認q 上的籌 碼數(shù)是負的，其大小恰好等去其他所有頂點上的籌碼總數(shù)，這樣，整個圖的籌碼總 數(shù)為零 b i g g s 在文章【1 0 】里就使用了這樣的設定，他取定口點一t - 的籌碼數(shù)為 s ( 口) = 一s ( u ) 0 t ，g 籌碼發(fā)射游戲中給出的各種定義，在美元游戲中也有對應定義 定義2 3 如果除q 以外的每個頂點穢上的籌碼數(shù)都滿足0 s ( v ) d ( ) ，即 除了q 點之外都不能發(fā)射，則稱s 為穩(wěn)定態(tài) 定義2 4 一個發(fā)射序列稱為是q 一合法的，當且僅當序列中q 點發(fā)射時其它 的頂點都已經(jīng)不能發(fā)射。 定義2 5 若存在某個非空的g 一合法序列，使得狀態(tài)s 在經(jīng)過該序列的發(fā)射 之后又返回到自身，則稱狀態(tài)8 是循環(huán)態(tài) 顯然，從狀態(tài)8 開始，可以進行無限個口一合法序列的發(fā)射，在此過程中，8 是 會循環(huán)出現(xiàn)的 定義2 6 如果一個狀態(tài)既是穩(wěn)定態(tài)又是循環(huán)態(tài)，那么我們把它稱它是一個臨 界態(tài) 臨界態(tài)一定是穩(wěn)定態(tài)，但是穩(wěn)定態(tài)不一定是臨界態(tài)例如每個頂點上的籌碼 都為0 時，這顯然是一個穩(wěn)定態(tài)，但是卻不是臨界態(tài) 1 1 第二章網(wǎng)的臨界群和t u l l e 多項式 定義2 7 如果一個發(fā)射序列s 中q 點沒有被發(fā)射。則我們稱這個序列是合適 美元游戲是籌碼發(fā)射游戲的一個變形，所以大部分性質(zhì)在本質(zhì)上是相同的， 所以同樣有以下幾個性質(zhì)成立。 性質(zhì)2 2 2 在美元游戲中，任意給定一個狀態(tài)8 ，若它存在一個合適的口一合 法序列s ，則s 的長度是有上界的，即發(fā)射，必然在某個時候停止下來，不會無限的 發(fā)射下去 從籌碼發(fā)射游戲的角度來看，任意一個狀態(tài)8 ，在其中的口點不發(fā)射的情況下 也是不可能無限的發(fā)射下去的( 性質(zhì)2 1 4 ) ，必然會在有限步之后停下來 性質(zhì)2 2 3 對于任意的狀態(tài)8 ，存在臨界態(tài)c ，使得s 在經(jīng)過一個口一合法序列 的發(fā)射后能夠變?yōu)閏 在這里的8 本身并沒有任何要求，既可以不是穩(wěn)定態(tài)，也可以不是循環(huán)態(tài)，但 是在經(jīng)過個q 一合法序列的發(fā)射后，能夠變換成一個臨界態(tài)c ，而這正是我們所 研究的 定理2 2 4c 是一個循環(huán)態(tài)，如果經(jīng)過一個g 合法的發(fā)射序列s 的發(fā)射后它 又回到自身，則s 的表示向量u 是全一向量。 發(fā)射過程可表示為c l u = c ，所以上面的發(fā)射序列s 的表示向量u 也恰好 是l u = 0 的解，而l a p l a c i a n 矩陣的解空間是一維的，其中所有分量都相同，所以 牡是所有分量都相同的常向量也就是說，循環(huán)態(tài)c 經(jīng)過一系列發(fā)射后回到c 自 身，這個發(fā)射過程中，所有頂點發(fā)射的次數(shù)一定是相同的事實上，所有頂點都正 好發(fā)射了次， 定理2 2 5 臨界態(tài)c 經(jīng)過一個g 一合法序列s 的發(fā)射后變?yōu)榱硪粋€臨界態(tài)d ， 則c = d 從這個性質(zhì)中我們會發(fā)現(xiàn)，雖然任何一個狀態(tài)都可以通過頂點的發(fā)射到達某 個臨界態(tài)，但是一個臨界態(tài)卻不能通過頂點的發(fā)射到達另一個臨界態(tài)，發(fā)射后到 達的臨界態(tài)依然會是它本身 綜合上面兩個性質(zhì)，我們有 1 2 定理2 2 6 對于任意一個狀態(tài)s ，存在唯一的一個臨界態(tài)c ，使得8 在經(jīng)過一 第二章網(wǎng)的臨界群和t i 1 t e 多項式 個q 一合法序列的發(fā)射后能夠變?yōu)閏 這就意味著任意的一個狀態(tài)在合法序列發(fā)射的條件下都只有一個臨界態(tài)與 之對應所以我們可以用臨界態(tài)來將這些狀態(tài)進行分類，而臨界態(tài)就是每個類的 代表元 令伊( g ，z ) 和c 1 ( g ，z ) 分別是定義在頂點集y 和邊集e 上的整值函數(shù)， 它們可以視為向量空間中的向量，而關聯(lián)矩陣d 和它的轉(zhuǎn)置d t 則可視為如下向 量空間上的同態(tài) d ：伊( g ，z ) _ c 1 ( g ，z ) ， d ：c 1 ( g ，z ) _ c o ( g ，z ) 那么l a p l a c i a n 矩陣l = d d 2 可以看做是一個g o ( g ，z ) _ c o ( g ，z ) 的同 態(tài)，我們定義o ( y ) = e 射，( 鈔) ，那么盯就是伊( g ，z ) _ z 的同態(tài)在b i g g s 的文 章【9 】中證明了如下的性質(zhì) 定理2 2 7i mq 是k e r 盯的正規(guī)子群 對于每個狀態(tài)0 ，令7 ( 0 ) 表示與之對應的唯一的臨界態(tài)，由于任意一個態(tài)都 屬于k e r 盯，用【0 】表示p 關于i mq 的陪集，定義 r ：k e ra i mq k ( g ) ， 其中7 ( 0 1 ) = - r ( o ) ，k ( g ) 表示圖g 的臨界態(tài)所構成的集合除了這個定理， 文章【9 】還給出了如下結(jié)果 定理2 2 8 連通圖g 的臨界態(tài)的集合k ( a ) 與阿貝爾群k e rt r i mq 之間存 在一一映射 其中阿貝爾群k e r a i m q 的加法定義為：【叮+ 】= p + 9 ，】 k ( a ) 的加法定義 為：c c ，= 7 ( c + ) ，其中c 和c ，都是臨界態(tài) 這個由臨界態(tài)所構成的群就是我們所研究的l l 臺i 界群，通常就記為k ( g ) ，在 有些文章中也被稱為雅可比群( j a c o b i a ng r o u p ) 【l5 i l o r e n z i n i 在早期的文章【1 6 l 中已經(jīng)簡單介紹了一些臨界群的內(nèi)容c o d 在文章1 1 7 】中還證明了平面圖與其對 偶圖的臨界群之間的聯(lián)系 對于一個平面圖g ，它一定可以找到一個平面表示m 則g 的對偶圖伊是 以m 的面為頂點的圖，以相鄰的兩個面之間連一條邊 定理2 2 9 平面圖g 與它的對偶圖口有相同的臨界群 1 3 第二章圖的臨界群和嚇胛e 多項式 為了證明這個定理，我們需要用到邊集上的一個賦值考慮邊的一個定向賦 值u ，使得每條定向的邊所賦的值都是正整數(shù)，即對于任意的邊n ，w ( a ) z + ；如 果u ( o ) = 0 ，則不給這條邊定向若某條邊e 的賦值取負，方向也取相反，其他邊 的定向賦值不變，得到了定向賦值u 7 ，我們認為u = u ，即這兩個定向賦值是同一 個示意圖如下： 1 4 2 圖2 1 1 邊的一個定向賦值u 2 圖2 1 2 定向賦值= u 在定向賦值u 下，若e = 忱_ ，則稱e 為仇的出邊，為的入邊 第二章圖的臨界群和t i r r r e 多項式 這樣給的邊上的定向賦值，我們還可以誘導定義出頂點上的賦值o w 以及 面上的賦值擴u 它們分別如下： 對于頂點v i ，( 釓) t 等于釓的所有出邊的賦值之和減去所有入邊的賦值之和； 對于面 ，( 0 u ) t 等于面五的所有鄰邊的有向賦值和，即鄰邊e 的定向和正向 相同的，賦值取u ( e ) ，否則取一( e ) ( 一般取逆時針方向為正向) 圖2 2 誘導的頂點賦值孔 5 圖2 3 誘導的面賦值伊u 1 5 第二章圖的臨界群和n 臃多項式 定理2 2 1 0 若u 是連通圖g 的一個頂點賦值，滿足條件： u t = 0 i = 1 則一定存在邊上的賦值u 使得a ) = t 證明：要證明存在滿足條件的u ，只需要考慮圖g 的支撐樹即可，其他的邊可 以都賦零值 取定g 的支撐樹t ，則t 肯定存在根節(jié)點滿足條件：存在邊的某個定向， 使得任意一個頂點 都有到的有向路，即所有的邊都指向根節(jié)點顯然t 中連接u 和的路有且只有一條，所以在這樣的定向下，除了沒有出邊之外， 其他的任意頂點都有且只有一條出邊考慮如下的邊賦值u ： 若邊e 岳t ，則u ( e ) = 0 ： 若邊e 關聯(lián)到t 的某個垂點仇，則u ( e ) = u i ； 若邊e 是某個頂點優(yōu)的唯一出邊，則u ( e ) = u +u ( a ) 我們可以斷言，此就是滿足條件的邊定向賦值： 首先，由第一條，去掉其他邊，只需要考慮t 上的賦值即可 對于r 的所有垂點地，由第二條，蚴= u ( e ) = ( 釓) ； 若仇不是垂點，e 是它的唯一出邊，則 u 產(chǎn)( e ) 一 u ( 口) = ( 釓) t ； o 是仇的入邊 r t - 1 對于根結(jié)點，u n = 一= 一叫( o ) = ( 釓) t 口 訌l n 是的入邊 類似的，以下定理也成立 定理2 2 1 1 若礦是連通圖g 的一個面賦值，滿足條件： u 凈0 。i 。e ，：1 1 喜：薹：筆支蘭； l 0 否貝| j 第二章圖的臨界群和t i 丌_ r e 多項式 從向量的角度來看，其誘導頂點賦值o d i 恰好為矩陣l ( g ) 的第i 個行向量t ， 即a d i = a t ；而其誘導面賦值伊d i = 0 圖2 4 由頂點v 2 取定的邊定向賦值d 2 同樣的，對于某個面五，我們還可以取邊定向賦值叫如下： 。：c e ，= 冀：篙主曼翥；黧主寶； 和前一個結(jié)論類似的，其誘導面賦值礦d ：恰好為矩陣l ( g + ) 的第z 個行向量：， 即礦刪= ：；而其誘導頂點賦值o d ：= 0 1 7 第二章圖的臨界群和腳多項式 圖2 5 由面如取定的邊定向賦值d ： 參考文獻【1 8 l 給出了以下定理： 定理2 2 1 2g 是平面圖，u 是它的一個邊定向賦值，若o w = 0 ，則u 一定可 以表示成若干d ：的線性組合 現(xiàn)在，我們可以回過頭來證明定理2 2 9 了 定理2 2 9 的證明：設面是k ( g ) 的某個元素，則它必然對應了某個臨界 態(tài)讓，如同注釋2 2 1 所言，可以取定u i = 0 若將此臨界態(tài)視為頂點賦 值，則由定理2 2 1 0 ，存在邊定向賦值使得o w = u 定義臨界群之間的映射 妒：k ( a ) hk ( g + ) 如下 妒( 面) = 0 + u 其中瓦為擴u 對應的臨界態(tài)在k ( g ) 中的像 首先說明，這樣定義的妒是有意義的，即妒( - ) 不會因為“和u 的取值不同 而變化 由前面對臨界態(tài)的性質(zhì)的討論可知，瓦和心是一一對應的； 當u 取定的時候，若存在u 滿足釓= 批= 釓，則由定理2 2 1 2 ，u u 7 是 d i ，d ：的線性組合，從而必有 釓一o w 7 ， 前面已經(jīng)說了，o d ：= 0 ，所以 瓦= 麗：面 1 r 第二章圖的臨界群和，r 【，t t e 多項式 從而的取值不影響結(jié)果 接下來要說明，q o 是個一一映射事實上，由于a 和伊都是線性作用，所以妒 也是個線性作用： 對于臨界群k ( c ) 中的任意兩個元素面，可，存在邊定向賦值u 和t 滿足 釓= u ，挑= 秒，從而 妒( 瓦+ 蠆) = 伊0 + t ) = 0 + u + 0 t 臨界群k ( g ) 和k ( g + ) 都只有一個單位元，所以妒只能是一一映射了口 事實上，臨界群k ( a ) 是一個有限生成的阿貝爾群，具有如下形式的直和分 解 k ( g ) = ( z n , z ) o ( z n 2 z ) o o ( 糾珥z ) 其中的吼就是本文提到的不變因子，滿足條件整除啦+ 1 要確定這些不 變因子就等于在確定關系矩陣l ( g ) 的s m i t h 標準型，其對角線上的元素就