簡(jiǎn) 純 ，李國(guó)全

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

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

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

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

設(shè)m∈N，H為一個(gè)以V1，V2，…，Vl為頂點(diǎn)類的l-部k-圖，稱H為m-均衡的，如果|V1|=|V2|=… =|Vl|=m.

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

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

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

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

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

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

定義4設(shè)H為一個(gè)2-均衡3-部3-圖，v（H）=1.稱H為一個(gè)極圖，如果對(duì)于任何一個(gè)2-均衡3-部3-圖H′，當(dāng) v（H′）=1時(shí)，必有|E（H′）|≤|E（H）|.

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

圖1 極圖HFig.1 Extreme graph H

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

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

H為一個(gè)極圖?|E（H）|=4

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

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

充分性：顯然.

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

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

由引理及其證明可知，?1≤ i≤ 4，|E（H）∩Mi|=1.從 M1，M2，M3，M4中各取一條邊，總共能形成16個(gè)圖形 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ù)的定義，易見(jiàn)這些圖的匹配數(shù)均為1.因此，它們都是極圖.現(xiàn)只需說(shuō)明 H4，H5，…，H15，H16中的每一個(gè)必與H1，H2，H3之一同構(gòu).

對(duì)于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）為一個(gè)同構(gòu)映射，從而H1≌H4.

對(duì)于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）為一個(gè)同構(gòu)映射，從而 H1≌H5.

對(duì)于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）為一個(gè)同構(gòu)映射，從而 H1≌H6.

對(duì)于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）為一個(gè)同構(gòu)映射，從而 H1≌H7.

對(duì)于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）為一個(gè)同構(gòu)映射，從而 H1≌H8.

對(duì)于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）為一個(gè)同構(gòu)映射，從而 H2≌H9.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H2≌H10.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H2≌H11.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H2≌H12.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H2≌H13.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H2≌H14.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H2≌H15.

對(duì)于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）為一個(gè)同構(gòu)映射，從而H3≌H16.

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

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

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

[3] 王朝瑞.圖論[M].北京：北京理工大學(xué)出版社，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.