图与超图中的彩色匹配综述  

A survey on rainbow matchings in graphs and hypergraphs

作　　者：李瞳 王光辉[1] 周文玲 LI Tong;WANG Guanghui;ZHOU Wenling(chool of Mathematics, Shandong University,Jinan 250100,China)

机构地区：[1]山东大学数学学院

出　　处：《运筹学学报》2019年第3期77-90,共14页Operations Research Transactions

基　　金：国家自然科学基金(Nos.11471193,11631014,11871311);山东大学齐鲁学者基金

摘　　要：超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.A hypergraph H =(V,E)is a two-tuple(V,E),where the element in the hyperedge set E is a non-empty subset of the vertex set V.Therefore,the graph is a special hypergraph,and the hypergraph can also be regarded as a generalization of the general graph.In particular,if the elements in the hyperedge set E are all a k-subset of the vertex set V,then the hypergraph is said to be k-uniform.Usually,for the sake of simplicity,we will also refer to the hyperedge as the edge.A matching in a graph(hypergraph)refers to a collection of mutually disjoint edges in a graph(hypergraph).There are two ways to define a rainbow matching:one is a collection of mutually disjoint edges with different colors in an edge-colored graph(hypergraph);the other one is a collection of mutually disjoint edges with different colors,where each edge is from different edge-colored graphs(hypergraphs).This paper mainly introduces the results related to rainbow matchings in graphs and hypergraphs.

关 键 词：图 超图 匹配 彩色匹配 

分 类 号：O157.5[理学—数学]