几个最小2容错广播网络

广播是研究通信网络的某个成员的消息如何尽快地传递给所有其它成员的消息传递问题。有两种常见的通信模式,一类是shouting模式,即在一个单位时间内,一个顶点能够和它的所有邻点通信;另一类是whispering模式,即在一个单位时间以内,一个顶点最多只能和它的一个邻点通信。通信网络通常用图来描述。最初贮存消息的网络成员称为源点。一个极小k容错广播网络是指n个顶点的通信网络,它的每个成员都能在k条边失效的情形下在最小的时间T_k(n)内实现广播。T_s(n)定义为一个这样的最小整数,使得存在一个n阶网络,以该网络的任何顶点为源点都能在不超过T_K(n)个单位时间内执行k容错广播。B_k(n)是n阶极小k容错广播网络必需的通信线路的最小数目。本文提出了呼叫图的新概念,构造它可以直观地判断k容错广播方案的正确性,并且可以作为求解B_k(n)的一种有效的辅助手段,本文给出了一些B_2(n)值(n≤10)。