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

作者：梁作松; 管梅; 单而芳

来源：通化师范学院学报, 2010, (04): 5-8.

DOI：10.13877/j.cnki.cn22-1284.2010.04.002

• 团
• 最小团横贯集
• 最大团独立集
• 块图
• 算法 clique
• minimum clique transversal set
• maximum clique independence set
• block graph
• algorithm

图的一个极大完全子图称为图的一个团.若图G的每一个块为图G的一个团,则称图G为块图.求图的一个最小团横贯集问题和最大团独立集问题分别称为MCTS问题和MCIS问题.文中给出了块图中求解最小团横贯集和最大团独立集的一个线性时间算法,并证明了块图G中的团横贯数等于团独立数,即τC(G)=αC(G).

• 单位
  上海大学; 湛江师范学院基础教育学院; 合肥学院