平面二部圖的完美匹配和分配格結(jié)構(gòu).pdf

1、1988年，張?；热艘肓肆窍到y(tǒng)的完美匹配集合上的Z-變換圖(共振圖)的概念：兩個完美匹配相鄰當且僅當它們的對稱差是一個六角形．后來張和平等人將此概念推廣到了平面二部圖上，通過區(qū)分兩種不同的匹配交錯圈，給Z-變換圖進行了定向，從而建立了有向Z-變換圖．對于平面弱基本二部圖，他們證明其有向Z-變換圖無(有向)圈，以此建立了其完美匹配集合上的有限分配格結(jié)構(gòu)．并由此證明了每個連通的共振圖都是median圖，因此可等距離嵌入到超立方體中．Z

2、-變換圖的概念因其自然性也曾被Gr ündler，Randic和Forunier等人從不同角度獨立提出． 對于一個平面弱基本二部圖G，記M(G)是由其有向Z-變換圖確定的完美匹配集合上的分配格．我們稱一個有限分配格L是匹配型的，若存在平面二部圖G，使得L≌M(G)．然而非匹配型分配格確實是存在的．因此一個自然的問題是如何刻畫匹配型分配格．本文中我們從兩個方面研究了該問題，給出了若干類匹配型分配格和非匹配型分配格．根據(jù)著名的Bir

3、khoff有限分配格基本定理，分配格M(G)可由其并不可約元導出的子偏序集產(chǎn)生出來．因而，我們討論的第二個問題是如何刻畫M(G)的并不可約元．在本文中，我們通過在G的內(nèi)面的重集上建立偏序關(guān)系，給出了由M(G)的并不可約元導出的子偏序集的完整刻畫．由于匹配型分配格可嵌入到整點網(wǎng)格中．我們要問能使M(G)嵌入的整點網(wǎng)格的最小維數(shù)是多少．早在1998年，張和平猜想這個最小維數(shù)恰好是G的共振數(shù)．在本文中，我們利用前述對M(G)并不可約元的刻畫，

4、證明此猜想是正確的． 全文共分六章，第一章介紹了匹配研究的背景及一些基本概念和術(shù)語，綜述了目前在平面二部圖的完美匹配集合上的Z-變換圖和有限分配格結(jié)構(gòu)方面的主要進展和結(jié)果，并概述了本文得到的主要結(jié)論． 在第二章中，我們在2-連通外平面圖的內(nèi)面集合上建立了一個偏序關(guān)系，并利用偏序集上著名的Dilworth最小一最大定理證明了：覆蓋一個2-連通外平面二部圖G的基本邊割的最少個數(shù)和其Z-變換圖Z(G)的最大導出超立方體的維數(shù)相

5、等，并且這個數(shù)恰好是G的共振數(shù)．這是對Klavzar等人在Cata-型苯圖上發(fā)現(xiàn)的相應最小-最大定理的推廣． 在第三章我們考慮了兩類特殊的平面基本二部圖，2-連通外平面二部圖和截斷的平行四邊形六角系統(tǒng)，由此給出了兩類匹配型分配格：J(T)和J(W)，其中T是任意樹形偏序集，W是兩條鏈m，n的直積m×n的任意濾子，而J(P)是由P的所有濾子按反包含關(guān)系構(gòu)成的有限分配格． 在第四章中，我們通過刻畫帶割元的匹配型分配格的局部結(jié)

6、構(gòu)，給出幾類非匹配型分配格．我們證明若分配格L有一個m+n型割元且m，n≥3，或L有一個2+n型割元但不含一個特殊的子格，則L是非匹配型分配格．其中，稱分配格L中的一個非最大、最小元x為割元，若L中的所有極大鏈包含x；進一步，稱x是m+n型的，若L中恰有m個元素覆蓋x和n個元素被x覆蓋． 在第五章中，我們首先在平面基本二部圖G的內(nèi)面的重集上建立了一個偏序集F(G)，然后證明了M(G)≌J(F(G))．利用該結(jié)論，我們證明了能使分

7、配格M(G)嵌入的整點網(wǎng)格的最小維數(shù)恰好是G的共振數(shù)．另外，我們還證明了J(1×m×n)是匹配型分配格． 在第六章中，我們在一般偏序集P上建立了分配格的商格結(jié)構(gòu)和有向根樹(森林)結(jié)構(gòu)．我們證明，若在構(gòu)造J(P)的過程中限制一些元素時，得到的代數(shù)結(jié)構(gòu)是有限分配格的直和，且由其分支導出的等價關(guān)系是J(P)上的同余關(guān)系，因此這些分支可導出J(P)的一個商格．而對于分別由P和其對偶P<'*>構(gòu)造出的兩棵對偶根樹，我們證明它們具有相同的高