按信包传递最小普查图研究

普查是信息网络中结点之间的一种常见的也是重要的信息传递方式．在普查过程中，网络所有结点的信息按一定的约束条件传递到终结点．本文定义并讨论了按信包传递最小普查图ｐ－ｍｃｇ，给出了最小普查时间ｔｐ（ｎ）的公式，在讨论了最小普查图与最小广播图的关系之后，指出了识别一个图是否为最小普查图的问题是ＮＰ完全问题，而且对ｐ＝－１，２，３完全解决了ｐ－ｍｃｇ的构造问题，对ｐ＝２ｋ给出ｎ＝ｍ·２ｋ时，ｐ－ｍｃｇ的构造方法．