通化师范学院学报
通化師範學院學報
통화사범학원학보
JOURNAL OF TONGHUA TEACHERS COLLEGE
2010年
4期
5-8
,共4页
团%最小团横贯集%最大团独立集%块图%算法
糰%最小糰橫貫集%最大糰獨立集%塊圖%算法
단%최소단횡관집%최대단독립집%괴도%산법
图的一个极大完全子图称为图的一个团.若图G的每一个块为图G的一个团,则称图G为块图.求图的一个最小团横贯集问题和最大团独立集问题分别称为MCTS问题和MCIS问题,文中给出了块图中求解最小团横贯集和最大团独立集的一个线性时间算法,并证明了块图G中的团横贯数等于团独立数,即Tc(G)=αc(G).
圖的一箇極大完全子圖稱為圖的一箇糰.若圖G的每一箇塊為圖G的一箇糰,則稱圖G為塊圖.求圖的一箇最小糰橫貫集問題和最大糰獨立集問題分彆稱為MCTS問題和MCIS問題,文中給齣瞭塊圖中求解最小糰橫貫集和最大糰獨立集的一箇線性時間算法,併證明瞭塊圖G中的糰橫貫數等于糰獨立數,即Tc(G)=αc(G).
도적일개겁대완전자도칭위도적일개단.약도G적매일개괴위도G적일개단,칙칭도G위괴도.구도적일개최소단횡관집문제화최대단독립집문제분별칭위MCTS문제화MCIS문제,문중급출료괴도중구해최소단횡관집화최대단독립집적일개선성시간산법,병증명료괴도G중적단횡관수등우단독립수,즉Tc(G)=αc(G).
