本文首先给出了求树图T的完美邻域的多项式时间复杂度算法(A),并在此基础上证明了当s是T的任一完美邻域且▏S▏ =Θ(T),则s是T的一极大无冗余集。然后给出了由T的一极大无冗余集生成完美邻域集的多项式时间复杂度算法(B),并依此算法证明了若s为T的任一极大无冗余集,则T存在一独= 完美邻域集U且▏U▏≤▏S▏。
评论星级较低,若资源使用遇到问题可联系上传者,3个工作日内问题未解决可申请退款~