图的扩张因子和转发指标

论文摘要

在图论里,通常用图来表示一个网络结构,其中图的顶点代表网络的节点（处理机或交换中心）,边代表连接两个节点的链路（两个节点间承载信息流的线路或信道）。连通图中,从任意一个顶点到其它顶点都有路（由边构成）连接。连接所有有序顶点对的n（n-1）条路构成图的一个路由。网络（G,R）是由图G和G上的一个路由R所组成的。网络（G,R）的点（边）的负荷是指R中通过该点（边）的路的数量,网络（G,R）的转发指标ξ（G,R）（π（G,R））是指G所有顶点（边）的负荷的最大值;网络（G,R）的扩张因子是顶点割集和边割集的扩展。图的转发指标是用来度量网络中节点或链路的负荷,而图的扩张因子是用来度量网络的连通性的。本文得到了两个图的乘积图的转发指标和扩张因子的上、下界,进而把结果推广到n个图的乘积图上;计算了一些特殊的乘积图的扩张因子和转发指标的值（或界）;得到了有向图的扩张因子的上、下界,给出了达到这些界的图的刻画,另外还计算了有向圈的转发指标和扩张因子的值。

论文目录

第一章前言

第二章无向图的乘积图

2.1 介绍

2.2 两个图的乘积图

2.2.1 边扩张因子

2.2.2 点扩张因子

2.2.3 转发指标

2.2.4 扩张因子与转发指标的关系

2.3 多个图的乘积图

2.4 实例

第三章有向图

3.1 介绍

3.2 有向图

参考文献

附录和致谢

图的扩张因子和转发指标

论文摘要

论文目录

相关论文文献