圖的循環(huán)定向 基礎(chǔ)數(shù)學(xué)專業(yè) 研究生鄒騰指導(dǎo)教師彭聯(lián)剛 c l u s t e r 代數(shù)是近幾年才出現(xiàn)的一種代數(shù)，與代數(shù)學(xué)中很多學(xué)科和分支都有 廣泛的聯(lián)系。s f o m i n 和a z e l e v i n s k y - 定義并分類了有限型的c l u s t e r 代數(shù)， 而m b a r o t ，c g e i s s 和a z e l e v i n s k y 的一項(xiàng)工作說(shuō)明，對(duì)有限型的c l u s t e r 代 數(shù)的判定問(wèn)題又依賴于其相應(yīng)的圖是否可以定向并且給出了一個(gè)圖是否可定 向的判斷方法該方法對(duì)圖中所有圈上的邊依次排序編號(hào)，然后考察不同的圈 是否有不同的極大邊，或者是計(jì)算頂點(diǎn)、邊、圈和連通分支間的數(shù)量關(guān)系本文 給出另外一種判定方法，我們的方法主要是通過(guò)觀察頂點(diǎn)之間的鏈進(jìn)行 關(guān)鍵詞：c l u s t e r 代數(shù)有限型有向圖循環(huán)定向 c y c l i c a lo r i e n t a t i o n so fg r a p h s m a j o r ：p u r em a t h e m a t i c s g r a d u a t es t u d e n tlz o ut e n g s u p e r v i s o rlp e n gl i a n g a n g a b s t r a c t c l u s t e ra l g e b r a sa p p e a r e dj u s ts e v e r a ly e a r sa g o i th a sb e e ns h o w nt h a t c l u s t e ra l g e b r a sa r er e l a t e dt ov a r i o u ss u b j e c t s s f o m i na n da z e l e v i u s k y d e f i n e da n dc l a s s i f i e dt h ed u s t e ra l g e b r ao ff i n i t et y p e b yar e s u l to fm b a r o t ，c g e i s sa n da z e l e v i n s k y , f i n i t et y p ef o rac l u s t e ra l g e b r ad e p e n d so l lt h ec y c l i c a l o r i e n t a t i o no ft h ec o r r e s p o n d i n gg r a p h t h e yg a v eam e t h o dt od e c i d ew h e t h e r ag r a p hc a nb ec y c h c a l l yo r i e n t e d t h e i rm e t h o di se i t h e rt oc o n s i d e rt h el i n e a r o r d e ro ft h ee d g e ss u c ht h a td i f f e r e n tc h o r d l e s sc y c l e sh a v ed i f f e r e n tm a x i m a l e d g e s ，o rt oc h e c kt h en u m b e rr e l a t i o na m o n gt h ea m o u n to fv e r t i c e s ，e d g e s ， c y c l e sa n dc o n n e c t e dc o m p o n e n t s i nt h i sp a p e r ，w eg i v ea n o t h e rm e t h o dt o d e c i d ew h e t h 盯ag i v e ng r a p hc a nb ec y c l j c 枷yo r i e n t e d o u rm e t h o di st ou s e t h ec h a i n sb e t w e e nt w ov e r t i c e s k e y w o r d s ：d u s t e ra l g e b r a ，f i n i t et y p e ，c l i r e c t e dg r a p h ，c y c l i c a lo r i e n t a - 聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的 研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以 標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫 過(guò)的研究成果，也不包含為獲得四川大學(xué)或其他教育機(jī)構(gòu)的 學(xué)位或證書而使用過(guò)的材料。與我一同工作的同志對(duì)本研究 所做的任何貢獻(xiàn)均已在論文中作了明確的說(shuō)明并表示謝意。 本學(xué)位論文成果是本人在四川大學(xué)讀書期間在導(dǎo)師指導(dǎo) 下取得的，論文成果歸四川大學(xué)所有，特此聲明。 導(dǎo)師_ i j 璺1 惟著塹塵 二零零七年四月二十日 第一章緒論 s f o m i n 和a z e l e v i n s k y 在【1 1 】中引入了d u s t e r 代數(shù)，這是由所謂的 d u s t e r 變量生成的n 元多項(xiàng)式分式域的子代數(shù)，其目的是為了研究如k a s h i w a x a 和l u s z t i g 定義的量子范包絡(luò)代數(shù)的對(duì)偶典型基( 【2 2 1 1 7 1 7 2 0 ) 與代數(shù)群的 全正性( 【1 2 2 1 1 5 1 1 6 】) 之間的關(guān)系，同時(shí)也希望它能夠刻畫關(guān)于代數(shù)群的族 的經(jīng)典量子化坐標(biāo)環(huán)( 文獻(xiàn)【1 】給出了一個(gè)具體的例子) 進(jìn)一步研究表明d u s t e r 代數(shù)結(jié)構(gòu)的理論( 參見(jiàn)【1 6 1 0 ) 與以下幾方面都 有聯(lián)系： 表示論( 【2 7 】【5 】【4 】【9 】) 量子群( 【8 】) 泊松幾何( 【1 9 】) 箭圖的表示( 【3 】【2 3 】) 勞倫現(xiàn)象( 【1 4 】) 熱動(dòng)力b e t h ea n s a t zy - 系統(tǒng)( 【i s ) 關(guān)于有限根基的一族凸多面體( 【2 4 1 1 2 5 1 ) 在【1 3 】中，s f o m i n 和a z e l e v i n s k y 對(duì)有限型的d u s t e r 代數(shù)進(jìn)行了分 類，其中將一個(gè)c l u s t e r 代數(shù)與一個(gè)反對(duì)稱矩陣相對(duì)應(yīng)m b a r o t ，c g e i s s 和 a z e l e v i n s k y 在【2 】中證明了d u s t e r 代數(shù)為有限型當(dāng)且僅當(dāng)其相應(yīng)的反對(duì)稱矩 陣b 對(duì)應(yīng)的有向圖可循環(huán)定向( 參見(jiàn)定義2 3 ) 且b 可導(dǎo)出一個(gè)正定的相交矩 陣所以若b 對(duì)應(yīng)的底圖( 即忘掉箭頭后的圖) 不可定向，則該d u s t e r 代數(shù)不 可能是有限型于是一個(gè)自然的問(wèn)題是如何判定一個(gè)圖是否可定向 b a r o t ，g e i s s 和z e l e v i n s k y 在f 2 】中( 定理5 1 ) 進(jìn)一步給出了一個(gè)圖r 是 否可定向的判斷方法他們的方法是對(duì)圖r 的邊依次排序編號(hào)。若存在一種編 四川大學(xué)碩士學(xué)位論文第2 頁(yè) 號(hào)的次序使圖r 中每個(gè)圈都有互不相同的編號(hào)極大的邊，則該圖可定向；或者 如果其頂點(diǎn)、邊、圈和連通分支間滿足一定的數(shù)量關(guān)系，那么圖r 可定向 上面那些方法均要求先觀察出所有的圈，本文給出了另一種方法，主要是 通過(guò)鏈( 參見(jiàn)定義3 1 ) 來(lái)判斷，這樣只需要對(duì)該圖特殊的頂點(diǎn)之間的鏈進(jìn)行觀 察即可 第二章預(yù)備知識(shí) 首先讓我們回憶一下【1 l 】中有關(guān)c l u s t e r 代數(shù)的基本內(nèi)容任給一個(gè)正整數(shù) n ，一個(gè)秩為n 的d u s t e r 代數(shù)是一個(gè)有單位無(wú)零甚子的交換環(huán)，并且還有一族稱 為c l u s t e r 變量的生成子d u s t e r 變量的集合是一系列互不相同的稱為d u s t e r 的n 元子集之并，這些d u s t e r 之間有如下的交換關(guān)系： 對(duì)于任意的d u s t e rx 和任給z x ，都一定存在一個(gè)d u s t e rx 7 是由 d u s t e r 變量一替換x 得到，而z 和一間有如下的二項(xiàng)式交換關(guān)系； z 毒= m l + m 2 此處m 1 和肘j 為互素的單項(xiàng)式。他們以x 一( z ) 為不定元進(jìn)一步，任意 兩個(gè)d u s t e r 之間均可以用一系列的這種變換得到 一個(gè)秩為n 的c l u s t e r 代數(shù)對(duì)應(yīng)一個(gè)n 正則樹死所謂n 一正則樹即該 樹中每個(gè)頂點(diǎn)有n 條邊與之相連c l u s t e r 代數(shù)中一個(gè)d u s t e r 對(duì)應(yīng)圖中一個(gè)頂 點(diǎn)，且對(duì)于圖中一條邊t 上，不妨設(shè)頂點(diǎn)t 和r 分別對(duì)應(yīng)d u s t e r x t 和五， 則它們之間僅有巧與弓不同且滿足； 巧= m a t ) + m j ( r ) 這里的兩個(gè)單項(xiàng)式 乃( t ) 和塢( r ) 是以集合五一 巧) 中的d u s t e r 變量為不定 元的互素的單項(xiàng)式故對(duì)邊t r ，有m j ( t ) 毛( r ) 仍為單項(xiàng)式，即有： 器m j = p 揣j ( t 聰水 ) ( 7 )7 ) p 、 、 此處( ) z 因?yàn)閴]( t ) 和嶼( 亡，) 以五中元為不定元，故i 取值從1 到n 已知底圖死中任一點(diǎn)均與n 條邊相連，而對(duì)于每一條邊均可如上做一個(gè)交換 單項(xiàng)式之比，故( ”) 中b i j ( t ) 的腳標(biāo)j 亦可從1 到取值從而得到n 竹 整數(shù)矩陣b ( t ) = ( b o ( ) 甜，稱為與頂點(diǎn)t 相對(duì)應(yīng)的矩陣進(jìn)一步， 易( t ) 和 嶼( r ) 實(shí)際上并不包含巧這個(gè)元，故它們的比中也不會(huì)出現(xiàn)巧，即( ) = 0 ， 四川大學(xué)碩士學(xué)位論文第4 頁(yè) j l ，2 ，n ) 同時(shí)，m j ( t ) 和m s ) 互索，故若尬( t ) 中出現(xiàn)不定元x k ， 則b k j ( t ) 0 ，而若 易( t ，) 中不出現(xiàn)不定元x r ，則b r j ( t ) = 0 所以： m a t ) = 所( t ) i iz 炒 i ：b 0 o m a t ) = 功( t ，) i i2 ， 個(gè)整數(shù)項(xiàng)方陣b = ( b i t ) 稱為符號(hào)反對(duì)稱的，如果。b o = = 0 或者b i j 和符號(hào)相反b = ( b o ) 和b 7 = ( 屹) 為同階整數(shù)方陣，稱b 7 由8 在k 方 向上做矩陣m u t a t i o n 得到，記為b 7 = 肌( b ) ，如果， 屹= 出學(xué)丑藉妒后 眨吡， 容易驗(yàn)證這里有肛0 p ；i d 而實(shí)際上，d u s t e r 代數(shù)中關(guān)于任意頂點(diǎn)t 的矩陣b ( t ) 均為符號(hào)反對(duì)稱的， 并且對(duì)于邊t t ，不妨設(shè)b ( t ) 和b ( e ) 分別表示點(diǎn)t 和r 對(duì)應(yīng)的矩陣，則： b ( e ) = 鯫( 日( t ) ) 反之，由【1 1 】中命題4 3 我們知道，對(duì)于給定的n - 正則樹 l ，一系列n 階整數(shù)方陣 b ( f ) ) * 可以如上對(duì)應(yīng)一個(gè)d u s t e r 代數(shù)當(dāng)且僅當(dāng) 其滿足如下條件t 1 ) 對(duì)任意t 死，b ( t ) 為反對(duì)稱矩陣 2 ) 對(duì)于邊t 與t ，則有，b ( r ) = i t k ( b ( t ) ) 由上述可知，一個(gè)c l u s t e r 代數(shù)對(duì)應(yīng)于一個(gè)符號(hào)反對(duì)稱的矩陣族 b ( t ) ) t e ，并且如果t 與在正則樹已中有邊相連，那么b ( t ) 和b ( e ) 可經(jīng)過(guò)一次的 m u t a t i o n 得到從而這族符號(hào)反對(duì)稱矩陣中的所有矩陣是m u t a t i o n 等價(jià)的我 們稱正則樹瓦中頂點(diǎn)t 和等價(jià)，如果相應(yīng)的符號(hào)反對(duì)稱的矩陣b ( t ) 和b ( t 7 ) 相等( 在同時(shí)交換相應(yīng)的行與列的意義下) 如果把c l u s t e r 代數(shù)相應(yīng)的n - 正則 樹中的頂點(diǎn)用頂點(diǎn)等價(jià)類代替，兩個(gè)等價(jià)類中如果有代表元相鄰則該兩個(gè)等價(jià) 類相鄰，如此得到c l u s t e r 代數(shù)的e x c h a n g e 圖而稱具有有限e x c h a n g e 圖的 c l u s t e r 代數(shù)為有限型 四川大學(xué)碩士學(xué)位論文第5 頁(yè) 對(duì)于一個(gè)n 階符號(hào)反對(duì)稱矩陣b ( t ) = ( b i j ) ，作1 1 個(gè)頂點(diǎn)的有向圖如下： 如果幻 0 ，則有從頂點(diǎn)t 指向j 的一條邊，且賦權(quán)i b i j b j i l ，稱為該矩陣相應(yīng) 的邊權(quán)圖，記為r ( b ) 例2 1 對(duì)干5 階符號(hào)反對(duì)稱矩陣 相應(yīng)的邊權(quán)圖r ( b ) 為 b 隹引 1 3 4 定義2 1 圈的循環(huán)定向是該圈上所有邊的定向均為首尾相連的 例2 2 循環(huán)定向的三角形只有以下兩種 1 31 在本章的最后，我們給出兩個(gè)重要的定義 3 定義2 2 如果圖中一個(gè)滿子圖為圈，那么該滿子圖稱為c h o r d l e s s 圈 四川大學(xué)碩士學(xué)位論文第6 頁(yè) 定義2 3 對(duì)一個(gè)圖，若存在- - 4 定向使得其中每個(gè)c h o r d l e s s 圈都是循環(huán)定向 的，則稱該圖為可循環(huán)定向 m b a r o t ，c g e i s s 和a z e l e v i n s k y 在【2 】中證明了c l u s t e r 代數(shù)為有限型 當(dāng)且僅當(dāng)其相應(yīng)的反對(duì)稱矩陣b 對(duì)應(yīng)的有向圖可循環(huán)定向且b 可導(dǎo)出一個(gè)正 定的相交矩陣所以為了討論如何構(gòu)造有限型c l u s t e r 代數(shù)的問(wèn)題，我們下面研 究圖的可定向問(wèn)題 第三章主要結(jié)論 約定下面簡(jiǎn)稱c h o r d l e s 8 圈為圈，一般的圈則特別說(shuō)明圖可循環(huán)定向簡(jiǎn)稱 為可定向 定義3 1 設(shè)1 1 ，赴，i 3 毛是圖中互不相同的頂點(diǎn)且t 3 若這t 個(gè)頂點(diǎn)間除可 能的邊 i 1 ，赴) 外其余的邊有且僅有 略，毛件1 ) p l 以t 一1 ) ，則稱為連接i l ，蟊的 一條鏈，記為( i l ，i 2 蟊) 一 此處的定義與b a r o t ，g e i s s 和z e l e v i n s k y 在【2 ( p 1 7 ) 中的定義略有不 同，他們要求t 1 與赴之間一定沒(méi)有邊 稱一個(gè)圈上的兩個(gè)箭頭為相容的，如果它們均為順時(shí)針或逆時(shí)針的否則， 稱它們互斥稱鏈被一條路所蘊(yùn)含，如果該鏈上的所有頂點(diǎn)均在該路上顯然長(zhǎng) 度大于等于2 的路總是蘊(yùn)含鏈 定義3 2 稱兩點(diǎn)間幾條鏈為本質(zhì)互異的，如果任一條鏈一定包含其余幾條鏈之 外的點(diǎn) 譬如 a ! 夕i 。 該圖中點(diǎn)a ，b 問(wèn)的鏈( a ，1 ，2 ，6 ) ，( a ，3 ，2 ，( 吼3 ，4 ，6 ) 就不為本質(zhì)互異的，因?yàn)樯?面的鏈( o ，3 ，2 ，b ) 上的點(diǎn)均在其余兩條鏈上 四川大學(xué)碩士學(xué)位論文第8 頁(yè) 顯然。滿子圖如果不可定向，則該圖不可定向 完全圖( 任意兩點(diǎn)之間均有且僅有一條邊相連) 的定向是很清楚的：易知 小于四點(diǎn)時(shí)都可定向，并且至少4 個(gè)點(diǎn)的完全圖是不可定向的因?yàn)樗欢ò?含4 點(diǎn)完全圖為滿子圖，而4 點(diǎn)完全圖 一定不可定向故下面都不考慮完全圖，即下面的圖都不是完全圖 引理3 1 兩圈之間若有相鄰兩條及以上的公共邊，則該圖一定不可定向 證明；當(dāng)有相鄰兩條公共邊時(shí)，如下圖 專。兮耄 蟊南紗矗 其中設(shè)圈a 為0 ，鼻k ， l 矗 ，g 為0 ，j ，k ，j l 靠) 且公共邊僅為0 ，j ， ( ，j ) ，若0 - 如) 與 j - 易) 之間沒(méi)有邊，則0 ，i ，赴，j ，j - 如) 為 個(gè)圈g ，此時(shí)a ，q 和g 無(wú)法同時(shí)定向否則若0 ，i 1 矗，k ，j ，j - 矗) 不為一個(gè)圈，即a z 矗) 與 j 矗 之間有邊相連，取邊協(xié)，矗) 使得r + 8 最小，則 i ，t 1 露，矗j 1 ) 必為一個(gè)圈g ，此時(shí)仍有q ，g 和島無(wú)法 同時(shí)定向 假設(shè)圈a 和g 除公共邊0 ，j ) ，j 外還有至少一個(gè)公共點(diǎn)，總可以適 當(dāng)?shù)倪x取公共點(diǎn)使得露= 五中的r 最大，易知此處r t ，s p ，那么或者 四川大學(xué)碩士學(xué)位論文第9 頁(yè) 4 蟊，靠矗，為一個(gè)圍c 3 ，或者協(xié)魂，和協(xié)丘 間有邊相 連，選取邊 如，矗) 使得a + b 最大，則 吒i t ，七，矗矗) 為一個(gè)圈g ， 對(duì)這兩種情況都有圈a 。島和島無(wú)法同時(shí)定向 對(duì)于相鄰的公共邊更多的情況可以類似的討論 引理3 2 相交于一邊0 ，j ) 的兩圈之間，不能有任何不過(guò)交點(diǎn)i 或j 的路分別 連接兩圈上非t ，j 的點(diǎn) 證明：如圖； i 1j 1 i l i； ；l i ij ； i ； 釓 昴 設(shè)圈a 為 t ，j ，i 1 矗) ，圈q 為a ，j ，j l 如) 且公共邊為0 ，j ) 若兩圈除點(diǎn)i ，j 外還有交點(diǎn)，即該兩點(diǎn)由長(zhǎng)度為0 的路相連接總可以取最 小的i 。使得i 。= 如，此處a 1 1 ，t 一1 ) b 1 1 ，p 一1 ) ，否則比如a = 1 ，b 1 則，點(diǎn)i 和如之間有邊相連，故使得 i ，j ，j 1 靠) 不是c h o r d l e s s 圈此時(shí) 如果 i 1 站) 和d l j 6 ) 之間沒(méi)有邊，則 t ，i t i 。，如_ 1 j 1 ) 為一 個(gè)圈島，則a ，q 和c j 不能同時(shí)定向否則， 1 1 站) 和 j - 九) 之間有邊，取邊協(xié)，矗) 使得r + 8 最小，則 t ，i l ， j 1 ) 必為一個(gè)圈 島，則a ，q 和g 不能同時(shí)定向 若兩圈除點(diǎn)i ，j 外沒(méi)有交點(diǎn)，但非交點(diǎn)有長(zhǎng)度為1 的路相連，即0 l 蟊 和 j 1 矗) 之間有邊，則類似引理2 1 中的證明過(guò)程 故兩圈之間僅有公共邊0 ，j ，而且0 蟊) 和 j - 矗 之間沒(méi)有邊 若有長(zhǎng)度至少為2 的路連接非交點(diǎn)的兩點(diǎn)。則一定有鏈連接該兩點(diǎn)不妨設(shè)為 有鏈( 站，k 1 肆，j r ) 連接點(diǎn)以， ，s 1 ，q ，r 1 ，p j ，則取使得0 1 如， 和( 七1 辟) 之間有邊 如，) 的最小的i 。，和最小的矗使得有邊 如，) ， 四川大學(xué)碩士學(xué)位論文第1 0 頁(yè) 且取，使得一k 。最小如圖 、j 7 如矗 若此時(shí)鏈( i 。，如) 與鏈( i ，i l i 。，如j - ) 拼成一個(gè)圈g ( 此時(shí)可 能有i l = 。，島= ，j 1 = 如) ，則白，島和g 無(wú)法同時(shí)定向否則，該構(gòu)造 過(guò)程保證僅可能點(diǎn)i 和 k ) 之間還有邊，設(shè)為a ，k ) ，“。) ， 則顯然a ，i l t 。，砬。) ，“k i ，：) ，0 ，k k ，血j - ) 均 為圈 考慮由 a 睪，i ，i l 蟊，j ，靠j 1 ) 組成的滿子圖，僅可能 與 i 。如，歹，矗如) 之間還有邊，故該滿子圖中i 點(diǎn)上的所有 邊( f ，訂，億e - 】，“矗 ，0 ， a ，島。) 均同時(shí)屬于至少兩個(gè)圈由【2 j 2 中引 理5 6 ，可定向圖中，一個(gè)點(diǎn)上若有邊，則該點(diǎn)上一定有邊僅屬于一個(gè)圈故該 滿子圖不可定向，從而原圖不可定向 引理3 3 不相鄰兩點(diǎn)間若有三條本質(zhì)互異的鏈，則該圖不可定向進(jìn)一步地， 不相鄰兩點(diǎn)間的鏈條數(shù)大于等于了，則該圖一定不可定向 證明：設(shè)點(diǎn)i j 問(wèn)有三條鏈o 1 ( i ，i l ，如如，j ) ，0 2 ( t ，j l ，如靠，j ) 和 印( i ，1 ，j c 2 k ，j ) ，如圖； h k 州n 唰靠v 簟_ 缸 四川大學(xué)碩士學(xué)位論文第1 1 頁(yè) 不妨設(shè)盯1 ，觀和0 r 3 之間除去i ，j 外無(wú)交點(diǎn)否則，如i ，= 丘則，取i ，為新的i 點(diǎn)，并且把鏈( i - 4 一1 ) 并入c r 3 中，取該路中蘊(yùn)含的鏈為新的毋，取鏈毋 為( i ，蟊) 鏈o 2 為0 。矗) ，則該盯，觀和鉑還是本質(zhì)互異的 若u 1 和o 2 不能組成一個(gè)圈，則必定有邊 i 。 。) ，r l 【1 ，司，8 1 【1 ，p 】則 由盯- uo 2 上的點(diǎn)構(gòu)成的滿子圖中必定會(huì)有兩個(gè)僅相交于一條邊的圈a ，q 不 妨設(shè)交線為 站，矗) ，且邊 t 。，如+ 1 ) cq ， j b ，矗一1 ) cc 2 ，則有圈a 上點(diǎn) i 。+ l 和島上點(diǎn)如一1 由路t i 葉l 如，j ，k q 七1 ，t ，j 1 矗一1 ) 連接，故由引 理2 2 知，該圖不可定向 由上面的討論易知，當(dāng)不相鄰兩點(diǎn)間的鏈條數(shù)大于3 時(shí)，該圖不可定向 定理3 1 非完全圖可定向當(dāng)且僅當(dāng)圖中任意不相鄰兩點(diǎn)問(wèn)至多有2 條本質(zhì)互異 的鏈 必要性的證明：由引理( 3 3 ) 直接可得 至于充分性的證明，還需要一點(diǎn)準(zhǔn)備易知圖上定向的傳遞能且只能通過(guò) 恰相交于一邊的圈來(lái)完成一系列僅相交于一邊的圈若可定向，其上有且僅有 兩種定向?qū)嶋H上。若有一種定向使其上所有的圈均被定向，則將其上每條邊的 方向均翻轉(zhuǎn)即得另一種定向此時(shí)其上任意一條路中每條邊均被定向，實(shí)際上 此時(shí)給該路上任一邊賦予一個(gè)方向，則每條邊都被唯一的定向，故稱該路為傳 向路 引理3 , 4 相交于一條邊的兩圈有除公共邊外的交點(diǎn)，則該圖中存在不相鄰兩點(diǎn) 間有至少三條本質(zhì)互異的鏈 證明t 設(shè)兩圈為0 ， i l ，i 2 矗) 和( 1 j ，j l ，如矗 ，公共邊為a ，j ) ，如 圖： 四川大學(xué)碩士學(xué)位論文第1 2 頁(yè) q ；j 1 二t l 赴 除公共邊a ，j ) 外有交點(diǎn)i 。= 如。這里a 1 ，以b 1 ，r 否則，比如 a = t ，b = r ，則邊托，j ) 也為公共邊放點(diǎn)i 和赴之間就有( i ，i l ，i 2 赴) ， ( i ，j l , 如屯) 和( i ，工西) 三條本質(zhì)互異的鏈 當(dāng)= 1 ，b = l 時(shí)可以類似的推導(dǎo)而當(dāng)a = 1 ，b 1 時(shí)，則邊 t ，j b 會(huì) 使0 ，互j l ，j 2 矗) 不是一個(gè)c h o r d l e s s 圈，矛盾當(dāng)o 1 ，b = 1 時(shí)，可以類 似的推導(dǎo)故有a 1 ，t ) b 1 ，r ) ，所以i 。和j 之間有三條本質(zhì)互異的鏈 ( i 。，t 。1 i l ，i ) 。，矗一1 j l ，t ) 和( 矗，辦+ 1 且，j ，t ) 引理3 5 僅相交于一條邊的兩圈，若有非交點(diǎn)的兩點(diǎn)相鄰，則該圖中存在不相 鄰兩點(diǎn)聞?dòng)兄辽偃龡l本質(zhì)互異的鏈 證明：設(shè)兩圈為 t ，工i l ，i 2 缸) 和0 ，工j l ，j 2 矗) ，公共邊為 i ，連接 相鄰兩點(diǎn)的邊為 如，如) 如圖： 亂1 “i 、 o b 羔 。 j r 則i ，j ，知，矗四點(diǎn)中必有兩點(diǎn)不相鄰，否則該四點(diǎn)就構(gòu)成四點(diǎn)完全滿子圖不妨設(shè) 知與j 不相鄰，則必存在i p + l 使：( i p ，知+ l i t , j ) 為一條鏈，而( 知i l ， ，j ) 澎 四川大學(xué)碩士學(xué)位論文第1 3 頁(yè) 為第二條，而路 知，九，九+ 1 矗，j ) 中顯然蘊(yùn)含一條與前兩條本質(zhì)互異的鏈， 故知與j 之間至少有三條本質(zhì)互異的鏈 定理( 3 1 ) 充分性的證明t 若該圖不可定向，即圖中必有一個(gè)圈g ，其上至少有兩條互斥定向的邊 t ，j ) ，q ) ，而且 七，q ) 的定向一定是由托j ) 傳遞并決定，否則可以改變 七，q ) 及其相關(guān)的定向使得邊托j 七，訂的定向相容但定向只能通過(guò)僅交于一條邊 的兩圈傳遞，故要使托j ) 的定向傳遞到 七，g ) 上，則一定存在圈qnc 1 = 邊 i ， ，且不妨設(shè)有邊 工o ) cc 2 ， j ，6 ) ca ，則可以斷言頂點(diǎn)a ，b 一定由 不全在g u 島上的路連通如圖： ：二南 ；l i ：_ 7 9 斷言：連通頂點(diǎn)o ，b 的路中一定有路不過(guò)交點(diǎn)i ，j 不妨設(shè)傳向路p 1 過(guò)交點(diǎn) i ，且在交點(diǎn)i 上有邊0 ，站) i ，站 則要把方向從 i ，i 。) 傳遞到 i ，如) 上，或 者托如) 和0 ，講在一個(gè)圈a ，站，站，i l 蟊) 內(nèi)或者有圈 t ，i 。，礙吃) ， 0 ，四，t ，畦琺) ， i ，t ，礙吃) 0 ，砰，四吃) ，a ，四，i b ，i 2 氌) ， 如圖 諺一年i i 四 j - ! f 一 吒 夕如 故用路 i a , i l 如，講或 缸，曙吃嘿魄，i 2 ，i b ) 替換掉路p l 中的 如，i ，砧則得一條不過(guò)點(diǎn)i 的路即可 四川大學(xué)碩士學(xué)位論文第1 4 頁(yè) 由上知連通a ，b 的路中一定有不過(guò)交點(diǎn)的，故一定蘊(yùn)含不過(guò)交點(diǎn)的鏈q 若 鏈q 的頂點(diǎn)全在au c t 上，即圈a ，島上一定有除交點(diǎn)外的兩點(diǎn)相鄰，由引 理2 6 。存在不相鄰兩點(diǎn)間有至少三條本質(zhì)互異的鏈，此時(shí)，結(jié)論成立否則鏈 q 包含au 傷外的點(diǎn)而路q 1 o t k ，q 6 ) 和0 2 ，j ，6 ) 也為兩 條本質(zhì)互異的鏈，否則，僅可能路缸i k ，q 6 ) 不為鏈，此時(shí)由引理 2 6 ，知該圖中存在不相鄰兩點(diǎn)間有至少三條本質(zhì)互異的鏈易知a ，b 問(wèn)q ， q l 和q 2 這三條鏈為本質(zhì)互異的，故充分性得證 注3 1 對(duì)相鄰的兩點(diǎn)a ，b ，則可以有任意多條本質(zhì)互異的鏈而該圖仍可定向 比如l 8 該圖中相鄰點(diǎn)a ，b 間有盯1 ，0 2 ，0 3 ，幾四條鏈，他們均與邊b _ o 組成了 c h o r d l e s s 圈，而且如上圖所示進(jìn)行定向，從而能夠被同時(shí)定向?qū)嶋H上，此時(shí) a ，b 間可以有任意條由。指向b 的鏈 下面討論應(yīng)用該定理的例子 例3 1 對(duì)于圖 四川大學(xué)碩士學(xué)位論文第1 5 頁(yè) i 漲i。! ! 漲s 彩3 參考文獻(xiàn) 【l 】1 b e r e n s t e i na ，f o m i ns ，z e l e v i n s k ya c l u s t e ra l g e b r a si i i u p p e rb o u n d s a n dd o u b l eb r u h a t c e l l s ，p r e p r i n t m a t h r t 0 3 0 5 4 3 42 0 0 3 【2 】b a r o tm ，g h l s sc ，z e l h v i n s k ya c l u s t e ra l g e b r a so ff i n i t et y p ea n dp o s - i t i v es y m m e t r i z a b l em a t r i c e s 【j 】l o n d o nm a t h s a c , 2 0 0 6 ，n o 3 ：5 4 5 - 5 6 4 【3 】b u a na b ，m a r s hr ，r e i n e k em ，e ta l t i l t i n gt h e o r ya n dc l u s t e rc o m b i - n a t o r i o s 【j 】a d v m a 如2 0 0 4 ，n o 1 ：1 - 5 6 【4 】b u a na ，m a r s h r a n dr e i t e n i ，c l u s t e r t i l t e da l g e b r a s ，m a t h r t 0 4 0 2 0 7 5 1 5 】b u a na ，m a r s h r ，r e i n e k em ，r e i t e n a n dl a n dt o d o r o vg ，t i l t i n g t h e o r ya n dc l u s t e rc o m b i n a t o r i c s ，m a t h r t 0 4 0 2 0 5 4 【6 】b e r e n s t e i na ，z e l e v i n s k ya t o t a lp o s i t i v i t yi ns c h u b e r tv a r i e t i e s c o r n - m e n lm a t h h e l v ，1 9 9 7 ，1 1 0 7 2 ：1 2 8 - 1 6 6 吲b e r e n s t e i na ，z e l e v i n s k ya t e n s o rp r o d u c tm u l t i p l i c i t i e s ，c a a o n i c a lb a s e s a n dt o t a l l yp o s i t i v ev a r i e t i e s 叨i n v e n t m a t h ，2 0 0 1 ，1 4 3 ：7 7 - 1 2 8 【8 】b e r e n s t e i na ，z e l e v i n s k ya s t r i n gb a s e sf o rq u a n t u mg r o u p so ft y p e 山， i ni m g e l f a n ds e m i n a r a d v s o v i e tm a t h ，1 9 9 3 ，p a r t1 ：5 1 8 9 【9 】c a l d e r op ，c h a p o t o np a n ds c h i f f l e rr ，q u i v e r sw i t hr e l a t i o n sa r i s i n g f r o md u s t e r s ( a nc a ) ，m a t h r t 0 4 0 1 3 1 6 f l o c h a p t o nf ，f o m i ns ，z e l e v i n s k ya p o l y t o p a lr e a l i z a t i o n so fg e n e r a l i z e d a s s o c i a h e d r a 【j 】c a n a d a m a t h b u l l ，2 0 0 2 ，n o 4 5 ：5 3 7 - 5 5 6 【1 1 】f o m i ns ，z e l e v i n s k ya c l u s t e ra l g e b r a si ：f o u n d a t i o n s 【j 】a m e r m a t h s a c ，2 0 0 2 ，n o2 ：4 9 5 2 9 【1 2 f o m i ns ，z e l e v i n s k ya d o u b l eb r u h a tc e l l sa n dt o t a lp o s i t i v i t y 嘲a m e r m a t h s a c ，1 9 9 9 ，n o1 2 ：3 3 5 - 3 8 0 【1 3 1f o m i ns ，z e l e v i n s k ya c l u s t e ra l g e b r a s i i ：f i n i t et y p ec l a s s i f i c a t i o n j 】 2 0 0 2 【1 4 】f o m i ns ，z e l e v i n s k ya t h el a u r e n tp h e n o m e n o j 】a d v i na p p l i e dm a t h s ， 2 0 0 2 n o 2 8 ：1 1 9 _ 1 4 4 四川大學(xué)碩士學(xué)位論文第1 7 頁(yè) 1 1 5 】f o m i ns ，z e l e v i n s k ya t o t a lp o s i t i v i t y ：t e s t sa n dp a r a m e t r i z a t i o u s j m a t h i n t e l l i g e n c e r , 2 0 0 02 2 ，n o h2 3 - 3 3 【1 6 】f o m i ns ，z e l e v i n s k ya y - s y s t e m sa n dg e n e r a l i z e da s s o c i a h e d r a 吲a n n d ， m a t b ， ， 【l z f o m i ns ，z e l e v i n s k ya p a r a m e t r i z a t i o no fc a n o n i c a lb a s e sa n d t o t a lp o s i t i v e m a t r i c e s j a d v m a t h , 1 2 2 ( 1 9 9 6 ) ，4 9 - 1 4 9 【1 8 f o m i ns ，z e l e v i n s k ya y - s y s t e m sa n dg e n e r a l i z e da s s o c i a h e d r a ，a n n i n m a t h ，1 5 8 ( 2 0 0 3 ) ，9 7 7 - 1 0 1 8 【1 9 】g e k h t m a nm ，s h a p i r om ，v a i n s h t e i na c l u s t e ra l g e b r a sa n dp o s s i o n g e o m e t r yi j 】m a t h s p 0 k a cv i n f i n i t ed i m e n s i o n a ll i ea l g e b r a s 3 r de d i t i o n c a m b r i 婦eu n i v e r s i t y p 他s s 1 9 9 0 2 1 】l u s z t i gg i n t r o d u c t i o nt ot o t a lp o s i t i v i t y , i n ：p o s i v i t yi nl i et h e o r y ：o p e n p r o b l e m s 【嗍，d eg m 曠e re x p ，m a t h 2 毋d eg 礦e r , b