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

On Perfect Neighborhood and Irredundant Sets in Trees

中文关键词:  完美邻域集  无冗余集  独立  树.

英文关键词:perfect neighborhood set  irredundant set  independent  tree.

中文摘要:

      本文首先给出了求树图$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)$.