湛江师范学院学报
湛江師範學院學報
담강사범학원학보
JOURNAL OF ZHANJIANG NORMAL COLLEGE
2009年
3期
11-12,15
,共3页
团%团横贯数%团独立数%团图算法
糰%糰橫貫數%糰獨立數%糰圖算法
단%단횡관수%단독립수%단도산법
把图G的每一个团看作一个点, 两点之间有边相连当且仅当它们对应的团有非空交(即有公共点), 这样得到的图称为图G的团图, 记为K(G). 文章证明了如果一个图对应的团图为二部图,则该图的团横贯数等于团独立数, 即τc(G)=αc(G), 另外给出了判断一个图的团图是否为二部图的一个计算时间为o(n4)的多项式时间算法.
把圖G的每一箇糰看作一箇點, 兩點之間有邊相連噹且僅噹它們對應的糰有非空交(即有公共點), 這樣得到的圖稱為圖G的糰圖, 記為K(G). 文章證明瞭如果一箇圖對應的糰圖為二部圖,則該圖的糰橫貫數等于糰獨立數, 即τc(G)=αc(G), 另外給齣瞭判斷一箇圖的糰圖是否為二部圖的一箇計算時間為o(n4)的多項式時間算法.
파도G적매일개단간작일개점, 량점지간유변상련당차부당타문대응적단유비공교(즉유공공점), 저양득도적도칭위도G적단도, 기위K(G). 문장증명료여과일개도대응적단도위이부도,칙해도적단횡관수등우단독립수, 즉τc(G)=αc(G), 령외급출료판단일개도적단도시부위이부도적일개계산시간위o(n4)적다항식시간산법.
