谢挺,钟波,彭涛.关于树的完美邻域集与无冗余集 (英)[J].数学研究及应用,2007,27(1):13~18
关于树的完美邻域集与无冗余集 (英)
On Perfect Neighborhood and Irredundant Sets in Trees
投稿时间:2004-11-29  修订日期:2005-08-14
DOI:10.3770/j.issn:1000-341X.2007.01.003
中文关键词:  完美邻域集  无冗余集  独立  树.
英文关键词:perfect neighborhood set  irredundant set  independent  tree.
基金项目:
作者单位
谢挺 重庆工学院数理学院, 重庆 400050 
钟波 重庆大学数理学院, 重庆 400044 
彭涛 重庆大学数理学院, 重庆 400044 
摘要点击次数: 2762
全文下载次数: 2586
中文摘要:
      本文首先给出了求树图$T$的完美邻域的多项式时间复杂度算法(A),并在此基础上证明了当$S$是$T$的任一完美邻域且$\left|S \right| = \Theta (T)$,则$S$是$T$的一极大无冗余集.然后给出了由$T$的一极大无冗余集生成完美邻域集的多项式时间复杂度算法(B),并依此算法证明了若$S$为$T$的任一极大无冗余集,则$T$存在一独立完美邻域集$U$且$\left| U \right| \le \left| S\right|$.
英文摘要:
      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)$.
查看全文  查看/发表评论  下载PDF阅读器