互连网络转发指数和超连通度的分析

给定一个网络，转发指数问题是考虑满足网络中所有点对同时进行通讯时对网络的容量的最低的要求。而它的反问题是：对于一个网络，在给定点（或者边）容量的条件下，网络中最多能有多少个点对同时进行通讯，使得其点（或者边）的负载不超过其容量。.另外由于在网络的实际运行中，与同一个处理机直接相连的处理机(或连线)同时失灵的可能性实际上是很小的。那么在这种意义下，传统的连通度的概念就不能准确的刻画出网络的这一性质。所以为了更准确地度量网络的容错性，人们提出了图的超连通度和超边连通度的概念。.本项目计划研究网络转发指数的反问题和超连通度（超边连通度）。考虑其NP困难性，设计合适的算法。并研究它们与其它参数的关系以及在Cayley图，线图，正则图，笛卡尔乘积图中它们的上下界。