块图中的团横贯集和团独立集  

Clique Transversal Sets and Clique Independence Sets in Block Graphs

作　　者：梁作松[1] 管梅[2] 单而芳[3] 

机构地区：[1]湛江师范学院基础教育学院,广东湛江524300 [2]合肥学院数学系,合肥230000 [3]上海大学数学系,上海200444

出　　处：《通化师范学院学报》2010年第4期5-8,共4页Journal of Tonghua Normal University

基　　金：国家自然科学基金(基金号[10571117]);上海市曙光计划(基金号[06SG42])资助

摘　　要：图的一个极大完全子图称为图的一个团.若图G的每一个块为图G的一个团,则称图G为块图.求图的一个最小团横贯集问题和最大团独立集问题分别称为MCTS问题和MCIS问题.文中给出了块图中求解最小团横贯集和最大团独立集的一个线性时间算法,并证明了块图G中的团横贯数等于团独立数,即τC(G)=αC(G).Amaximal complete sub - graph of G is called a clique of G. If every block of G is a clique of G , then G is called a block graph. The problems of solving the minimum clique transversal set and the maximum clique independence set are called MCTS - Problem and MCIS - Problem respectively. This paper gives a linear - time algorithm of MCTS - Problem and MCIS - Problem in block graphs and proves that the clique transversal number equals the clique independence number in block graphs, that is τc（G）=αc（G）.

关 键 词：团 最小团横贯集 最大团独立集 块图 算法 

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