论文部分内容阅读
普查是信息网络中结点之间的一种常见的也是重要的信息传递方式,在普查过程中,网络所有结点的信息按一定的约束条件传递到终结点。本文定义并讨论了按信包传递最小普查图p-meg,给出了最小普查时间tp(n)的公式,在讨论了最小普查图与最小广播图的关系之后,指出了识别一个图是否为最小普查图的问题是NP完全问题,而且对p=1,2,3完全解决了p-meg的构造问题,对p=2^k给出n=m.2^k时p-meg的构