關于匹配數(shù)為1的極大2-均衡3-部3-圖的結構

簡 純 ，李國全

（1.天津師范大學數(shù)學科學學院，天津300387；2.陜西師范大學數(shù)學與信息科學學院，西安710062）

對于有限集A，記|A|為A中所含元素的個數(shù).設V為一個有限集，?k∈N，定義

定義 2[2]設 k、l∈N，l≥ k≥ 2.V1，V2，…，Vl為兩兩無交的有限集.稱k-圖H=（V，E）為一個以V1，V2，…，Vl為頂點類的 l-部 k-圖，如果并且?e∈E，?1≤j≤l，均有|e∩Vj|≤1.

設 H=（V，E）為一個以 V1，V2，…，Vl為頂點類的l-部k-圖，稱H為完全的，如果E=Vl為頂點類的完全的l-部k-圖為Kk（V1，…，Vl）.

設m∈N，H為一個以V1，V2，…，Vl為頂點類的l-部k-圖，稱H為m-均衡的，如果|V1|=|V2|=… =|Vl|=m.

定義3[3]設H為一個k-圖，M?E（H）.稱M為H中的一個匹配，如果?e1，e2∈M，當e1≠e2時，均有 e1∩e2= ?.

設H為一個k-圖，稱v（H）?max{|M|：M為H中的匹配}為H的匹配數(shù).

設H為一個k-圖，M為H中的一個匹配.稱M為最大的，如果|M|=v（H）；稱M為完美的，如果

眾所周知，在一個超圖中尋找最大匹配的問題在許多數(shù)學分支與計算科學中有著重要應用.此領域中一個最基本的問題是Erd?s[4]在1965年提出的：設k、，H為一個具有n個頂點的k-圖，試在條件v（H）＜t之下確定H所能具有的最大邊數(shù).對于一般情形，這是一個尚未解決的問題.

2011年 Markstr?m 等[5]對于 m-均衡的 k-部 k-圖完全解決了上述問題，并進一步說明：當m≥3時，具有最大邊數(shù)的極值超圖在同構意義下是唯一的；當m=2時，極值超圖在同構意義下是不唯一的.

上述結論表明：在匹配數(shù)為1的2-均衡k-部k-圖中能取到最大邊數(shù)的極值超圖是不唯一的.因此，可以進一步考慮：在同構意義下，存在多少個極值超圖.本研究在k=3的情形下回答這個問題.為此，引入主要研究對象：

定義4設H為一個2-均衡3-部3-圖，v（H）=1.稱H為一個極圖，如果對于任何一個2-均衡3-部3-圖H′，當 v（H′）=1時，必有|E（H′）|≤|E（H）|.

定理設 H 為一個以{1，2}、{a，b}、{α，β}為頂點類的極圖，則在同構意義下，H必為H1、H2、H3三者之一，如圖1所示，且H1、H2、H3互不同構.

圖1 極圖HFig.1 Extreme graph H

為證明定理，需要如下引理.

引理設 H為一個 2-均衡 3-部 3-圖，如果v（H）=1，則

H為一個極圖?|E（H）|=4

證明設H的3個頂點類分別為{1，2}，{a，b}和{α，β}.以{1，2}、{a，b}、{α，β}為頂點類的完全 3-部3-圖具有8條邊，這些邊恰好形成4個兩兩無交的完美匹配 M1={1aα，2bβ}，M2={1bα，2aβ}，M3={1aβ，2bα}，M4={1bβ，2aα}.

下面說明|E（H）|≤4.否則，由于|E（H）|≥5，則?1≤i≤4，使得 Mi?E（H），從而 v（H）≥|Mi|=2，矛盾.因此|E（H）|≤4.

充分性：顯然.

必要性：只需說明存在邊數(shù)為4的H滿足結論的條件即可.取 E（H）={1aα，1bα，1aβ，1bβ}，則 H滿足要求.

定理的證明H1中有一個頂點（頂點2）不位于任何邊上，H2中存在只位于1條邊上的頂點（頂點2與α），H3中每個頂點都位于2條邊上，因此，這3個圖是互不同構的.

由引理及其證明可知，?1≤ i≤ 4，|E（H）∩Mi|=1.從 M1，M2，M3，M4中各取一條邊，總共能形成16個圖形 H1，H2，…，H15，H16，其中：

E（H4）={1aα，1bα，2bα，2aα}

E（H5）={1aα，2aβ，1aβ，2aα}

E（H6）={2bβ，1bα，2bα，1bβ}

E（H7）={2bβ，2aβ，1aβ，1bβ}

E（H8）={2bβ，2aβ，2bα，2aα}

E（H9）={1aα，2aβ，1aβ，1bβ}

E（H10）={1aα，1bα，2bα，1bβ}

E（H11）={1aα，1bα，1aβ，2aα}

E（H12）={1aα，2aβ，2bα，2aα}

E（H13）={2bβ，1bα，2bα，2aα}

E（H14）={2bβ，2aβ，1aβ，2aα}

E（H15）={2bβ，2aβ，2bα，1bβ}

E（H16）={1aβ，2aα，2bβ，1bα}

由匹配數(shù)的定義，易見這些圖的匹配數(shù)均為1.因此，它們都是極圖.現(xiàn)只需說明 H4，H5，…，H15，H16中的每一個必與H1，H2，H3之一同構.

對于H4，定義f1：V（H1）→V（H4）為f1（1）=α，f1（2）=β，f1（a）=a，f1（b）=b，f1（α）=1，f1（β）=2，則映射 f1：V（H1）→V（H4）為一個同構映射，從而H1≌H4.

對于H5，定義f2：V（H1）→V（H5）為f2（1）=a，f2（2）=b，f2（a）=1，f2（b）=2，f2（α）=α，f2（β）=β，則映射 f2：V（H1）→V（H5）為一個同構映射，從而 H1≌H5.

對于H6，定義f3：V（H1）→V（H6）為f3（1）=b，f3（2）=a，f3（a）=2，f3（b）=1，f3（α）=β，f3（β）=α，則映射 f3：V（H1）→V（H6）為一個同構映射，從而 H1≌H6.

對于H7，定義f4：V（H1）→V（H7）為f4（1）=β，f4（2）=α，f4（a）=b，f4（b）=a，f4（α）=2，f4（β）=1，則映射 f4：V（H1）→V（H7）為一個同構映射，從而 H1≌H7.

對于H8，定義f5：V（H1）→V（H8）為f5（1）=2，f5（2）=1，f5（a）=b，f5（b）=a，f5（α）=β，f5（β）=α，則映射 f5：V（H1）→V（H8）為一個同構映射，從而 H1≌H8.

對于H9，定義f6：V（H2）→V（H9）為f6（1）=1，f6（2）=2，f6（a）=b，f6（b）=a，f6（α）=α，f6（β）=β，則映射 f6：V（H2）→V（H9）為一個同構映射，從而 H2≌H9.

對于H10，定義f7：V（H2）→V（H10）為f7（1）=1，f7（2）=2，f7（a）=a，f7（b）=b，f7（α）=β，f7（β）=α，則映射f7：V（H2）→V（H10）為一個同構映射，從而H2≌H10.

對于H11，定義f8：V（H2）→V（H11）為f8（1）=1，f8（2）=2，f8（a）=b，f8（b）=a，f8（α）=β，f8（β）=α，則映射f8：V（H2）→V（H11）為一個同構映射，從而H2≌H11.

對于H12，定義f9：V（H2）→V（H12）為f9（1）=2，f9（2）=1，f9（a）=b，f9（b）=a，f9（α）=β，f9（β）=α，則映射f9：V（H2）→V（H12）為一個同構映射，從而H2≌H12.

對于H13，定義f10：V（H2）→V（H13）為f10（1）=2，f10（2）=1，f10（a）=a，f10（b）=b，f10（α）=β，f10（β）=α，則映射f10：V（H2）→V（H13）為一個同構映射，從而H2≌H13.

對于H14，定義f11：V（H2）→V（H14）為f11（1）=2，f11（2）=1，f11（a）=b，f11（b）=a，f11（α）=α，f11（β）=β，則映射f11：V（H2）→V（H14）為一個同構映射，從而H2≌H14.

對于H15，定義f12：V（H2）→V（H15）為f12（1）=2，f12（2）=1，f12（a）=a，f12（b）=b，f12（α）=α，f12（β）=β，則映射f12：V（H2）→V（H15）為一個同構映射，從而H2≌H15.

對于H16，定義f13：V（H3）→V（H16）為f13（1）=2，f13（2）=1，f13（a）=b，f13（b）=a，f13（α）=β，f13（β）=α，則映射f13：V（H3）→V（H16）為一個同構映射，從而H3≌H16.

綜上所述，H4，H5，H6，H7，H8均與 H1同構；H9，H10，H11，H12，H13，H14，H15均與 H2同構；H16與 H3同構.

[1]BERGE C.Hypergraphs[M].Amsterdam：North-Holand，1989.

[2]BERGE C.Graphs and Hypergraphs[M].Amsterdam：North-Holand，1973.

[3] 王朝瑞.圖論[M].北京：北京理工大學出版社，1997.

[4] ERD?S P.A problem on independent r-tuples[J].Ann Univ Sci Budapest E?tv?s Sect Math，1965，8：93-95.

[5]MARKSTR?M K，RUCINSKI A.Perfect matchings（and Hamilton cyles）in hypergraphs with large degree[J].European J Combin，2011，32：677-687.