图的星匹配性质的研究

Research on Properties of Star Matchings of Graphs

摘要: 图的匹配理论是图论中的经典问题，它在实际生活中的应用也非常广泛.但传统的匹配理论只能解决一对一的人员分配问题，对于确定组长的多人分配问题传统的一对一匹配已无法解决，由此提出了星匹配的概念.完全二部图K_1,s称为星图.在图G中没有公共顶点的两个星子图K_1,s称之为相互独立的星子图，图G中相互独立的星子图所构成的集合M_K1,s（G）叫图G的一个K_1,s-匹配，简称星匹配.图G的所有星匹配中，含有K_1,s的最大个数称为图G的K_1,s-匹配数，简称星匹配数，记为m_K1,s（G），并称K_1,s-匹配为图G的最大K_1,s-匹配.若v是图G的某个最大K_1,s-匹配M_K1,s（G）中的顶点，则称M_K1,s（G）饱和了点v，若M_K1,s（G）饱和了图G的所有顶点，则称M_K1,s（G）为完美星匹配.本文利用分类讨论的方法研究了一些特殊图类具有星匹配的充要条件以及星匹配的上、下界；另外给出了二叉树和p叉树有完美星匹配的充分条件，并给出了二叉树以及p叉树的完美星匹配数的确切值.

Abstract: Matching theory in graph is a classical problem in graph theory, and also has very widely applications in real life. However, the traditional matching theory can only solve the problem of one-to-one personnel allocation, and the traditional one-to-one matching can not solve the problem of multi-person group allocation that determines the group leader, thus putting forward the concept of star matching. Complete bipartite graph K_1,s is called star graph. Two star graphs K_1,s without no common vertex in the graph G are called independent star graphs, and we call that the set M_K1,s（G） consisting of mutually independent star graphs K1;s is a K_1,s-matching of the graph G, simply star matching. The maximum cardinality of M_K1,s（G） is called K1;s-matching number of G, simply star matching number. We call that a vertex v of some maximum star matching M_K1,s（G） is saturated by M_K1,s（G）. If the maximum star matching M_K1,s（G） saturated all of vertices of G, then M_K1,s（G） is called perfect star matching. In this paper, by using the method of classification discussion, we present some bounds and necessary and sufficient conditions of containing star matchings in some special graphs; Moreover, we give the sufficient conditions of containing perfect star matchings in perfect binary trees and perfect p-ary trees, and give the exactly values of perfect star matching numbers of perfect binary trees and perfect p-ary trees.