| 关于树的完美邻域集与无冗余集 (英) |
| |
| 引用本文： | 谢挺,钟波,彭涛.关于树的完美邻域集与无冗余集 (英)[J].数学研究及应用,2007,27(1):13-18. |
| |
| 作者姓名： | 谢挺 钟波 彭涛 |
| |
| 作者单位： | 1. 重庆工学院数理学院,重庆400050
2. 重庆大学数理学院,重庆400044 |
| |
| 摘 要： | 本文首先给出了求树图T的完美邻域的多项式时间复杂度算法(A),并在此基础上证明了当S是T的任一完美邻域且｜S｜=θ(T),则S是T的一极大无冗余集．然后给出了由T的一极大无冗余集生成完美邻域集的多项式时间复杂度算法(B),并依此算法证明了若S为T的任一极大无冗余集,则T存在一独立完美邻域集U且｜U｜≤｜S｜．
|
| 关 键 词： | 完美邻域集 无冗余集 独立 树 |
| 文章编号： | 1000-341X(2007)01-0013-06 |
| 收稿时间： | 2004/11/29 0:00:00 |
| 修稿时间： | 11 29 2004 12:00AM |
On Perfect Neighborhood and Irredundant Sets in Trees |
| |
| XIE Ting,ZHONG Bo and PENG Tao.On Perfect Neighborhood and Irredundant Sets in Trees[J].Journal of Mathematical Research with Applications,2007,27(1):13-18. |
| |
| Authors: | XIE Ting ZHONG Bo and PENG Tao |
| |
| Institution: | School of Math. Phys., Chongqing Institute of Technology, Chongqing 400050, China;College of Math. Phys., Chongqing University, Chongqing 400044, China;College of Math. Phys., Chongqing University, Chongqing 400044, China |
| |
| Abstract: | For any tree $T$, we give an Algorithm (A) with polynomial time complexity to get the perfect neighborhood set in $T$. Then we prove that $S$, which is a perfect neighborhood set of $T$ and $|S|=\Theta (T)$, is also a maximal irredundant set in $T$. We present an Algorithm~(B) with polynomial time complexity to form the perfect neighborhood set from the maximal irredundant set in $T$, and point out that $T$ has an independent perfect neighborhood set $U$ and $|U|\le |S|~(|S|$ the cardinality of a maximal irredundant set of $T)$. |
| |
| Keywords: | perfect neighborhood set irredundant set independent tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《数学研究及应用》浏览原始摘要信息 |
| 点击此处可从《数学研究及应用》下载免费的PDF全文 |
|
