上海大学学报（自然科学版）
上海大學學報（自然科學版）
상해대학학보（자연과학판）
JOURNAL OF SHANGHAI UNIVERSITY (NATURAL SCIENCE EDITION)
2006年
1期
14-18
,共5页
二部置换图%控制集%无圈控制集%算法
二部置換圖%控製集%無圈控製集%算法
이부치환도%공제집%무권공제집%산법
设G=(V,E)为简单无向图,S()V称为G的无圈控制集,如果S控制G并且导出子图〈S〉不含有圈.该文证明了二部置换图的无圈控制数等于其控制数(γa(G)=γ(G)),利用此结论证明了无圈控制集问题在二部置换图上具有线性时间求解算法.
設G=(V,E)為簡單無嚮圖,S()V稱為G的無圈控製集,如果S控製G併且導齣子圖〈S〉不含有圈.該文證明瞭二部置換圖的無圈控製數等于其控製數(γa(G)=γ(G)),利用此結論證明瞭無圈控製集問題在二部置換圖上具有線性時間求解算法.
설G=(V,E)위간단무향도,S()V칭위G적무권공제집,여과S공제G병차도출자도〈S〉불함유권.해문증명료이부치환도적무권공제수등우기공제수(γa(G)=γ(G)),이용차결론증명료무권공제집문제재이부치환도상구유선성시간구해산법.
