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

MINIMUM CENSUS GRAPH BY PACKET OF SIZE p

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

Census taking is a message propagation process over a network whereby all the messages in the network have to be received at a particular unit.This paper defines and studies the minimum census graph by packet of size p(p-mcg)and presents the formula of minimum census taking time tp,(n). The relation between the minimum broadcast graph and the minimum census graph is discussed and the problem of recognizing whether a given graph is a p-mcg is proved to be NP-complete.Furthermore,some construction methods for p-mcg with p=1,2,3 and p=2k when n=m.2k is presented.