图论是设计和分析互连网络的最基本且强有力的数学工具.本文分为两大部分,第一部分对网络设计的三种基本方法进行介绍和分析,不管是无向图还是有向图,线图方法,笛卡尔乘积方法和Cayley方法都能保留原图的正则性.由线图方法和笛卡尔乘积方法得到的网络结构图其连通度都不会比原图小,且在特定条件下,线图和笛卡尔乘积图是Euler图和Hamilton图,含有欧拉回路和Hamilton圈的网络结构图具有简单的路由选择和存在有效的布图算法,因此在用线图方法或者笛卡尔乘积方法设计网络时,可以根据网络结构图同构可嵌入的特性,给原图适当增加一些边使得其线图或者笛卡尔乘积图含有欧拉回和Hamilton圈,这样可以增强网络的有效性和可靠性.用Cayley方法得到的网络结构图是点可迁的,其具有均匀性和对称性,并且Cayley图具有很强的可嵌入性.第二部分内容是介绍和分析超立方体网络和De Bruijn网络.不同的超立方体网络,连通性也不同,容错性也不同,但是,所有的De Bruijn网络的连通性和容错性都是相同的.超立方体网络具有均匀性和对称性,而De Bruijn网络存在唯一最有效的路由选择.

Graph theory is a fundamental and powerful mathematical tool for designing and analyzing interconnection networks. This paper is idivided into two parts, the first part includes introduce and analysis about the basic methods of the networks design. Line graphical methods, Cartesian product methods and Cayley methods can retain the original regularity whether the original graphs are undirected or directed. The connectivity of Line graphs and Cartesian graphs is not smaller than the original graphs. In particular, Line graph and Cartesian graph have Eulerian path and Hamilton cycle under some certain conditions, so we can add some edges on the original graphs when we construct netwok topological structures according to the theory of isomorphic embedding, hence such netwok topological structures have easy routing algorithm and efficient layout of VLSI circuits. In addition, Cayley graphs are vertex-transitive, and their embeddability is really strong. The other part introduces and analyzes the hypercube networks and de Bruijn networks. Different hypercube networks have different connectivity and different fault tolerance. However, different de Bruijin networks have the same connectivity and fault tolerance. In addition, hypercube networks have symmetry but de Bruijn networks have unique shortest paths.