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