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

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

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.