可靠通讯网络的构造

在可靠通讯网络的构造方面,F.Harary于1962年证明了“图Hm,n是m—连通的”的定理。此定理告诉我们,Hm,n是具有几个顶点,边数最少的m—连通图。 本文首先给出了连通正则图是m—连通的的充要条件,然后利用这一结果及循环图的性质,推广了“图Hm,n是m—连通的”这一定理,并构造出包含Hm,n在内的具有n个顶点、边数最少的一类m—连通图。最后利用同构的循环图构造出一类可靠通讯网络。