关于匹配数为1的极大2-均衡3-部3-图的结构

简 纯 ，李国全

（1.天津师范大学数学科学学院，天津300387；2.陕西师范大学数学与信息科学学院，西安710062）

对于有限集A，记|A|为A中所含元素的个数.设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的匹配数.

设H为一个k-图，M为H中的一个匹配.称M为最大的，如果|M|=v（H）；称M为完美的，如果

众所周知，在一个超图中寻找最大匹配的问题在许多数学分支与计算科学中有着重要应用.此领域中一个最基本的问题是Erdös[4]在1965年提出的：设k、，H为一个具有n个顶点的k-图，试在条件v（H）＜t之下确定H所能具有的最大边数.对于一般情形，这是一个尚未解决的问题.

2011年 Markström 等[5]对于 m-均衡的 k-部 k-图完全解决了上述问题，并进一步说明：当m≥3时，具有最大边数的极值超图在同构意义下是唯一的；当m=2时，极值超图在同构意义下是不唯一的.

上述结论表明：在匹配数为1的2-均衡k-部k-图中能取到最大边数的极值超图是不唯一的.因此，可以进一步考虑：在同构意义下，存在多少个极值超图.本研究在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.

充分性：显然.

必要性：只需说明存在边数为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α}

由匹配数的定义，易见这些图的匹配数均为1.因此，它们都是极图.现只需说明 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.