关于树的完美邻域集与无冗余集

• 作 者: 谢挺 钟波 彭涛
• 机 构: 重庆工学院数理学院,重庆大学数理学院
• 出 处: 数学研究与评论
• 发表日期: 2007年1期
• 关键词: 完美邻域集 无冗余集 独立 树 perfect neighborhood set irredundant set independent tree

本文首先给出了求树图T的完美邻域的多项式时间复杂度算法（A），并在此基础上证明了当S是T的任一完美邻域且｜S｜= θ（T），则S是T的一极大无冗余集．然后给出了由T的一极大无冗余集生成完美邻域集的多项式时间复杂度算法（B），并依此算法证明了若S为T的任一极大无冗余集，则T存在一独立完美邻域集V且｜U｜≤｜S｜．