Topological Structure and Analysis of Interconnection Networks
==========================================================================
Chapter
1
Interconnection
Networks and Graphs
The topological structure of an interconnection network can be modeled
by a graph. This fact has been universally accepted and used by computer scientists and engineers. Moreover, practically it has been
demonstrated that graph theory is a very powerful mathematical tool for designing and analyzing topological structure of interconnection
networks.
In this chapter, we will briefly recall some basic concepts and notation of graph theory used in this book as well as the
corresponding backgrounds of networks. Some basic results on graph theory will be stated, but some proofs will be omitted. For a
comprehensive treatment of the graph-theoretic concepts and results discussed herein, the reader is referred to any standard text-book on
graph theory, for example, Theory and Application of Graphs by Junming Xu. These
basic concepts include graph isomorphism, subgraphs, paths, connection,
adjacency matrix, embedding and planar graph, diameter, routing and
connectivity. In particular, Menger's theorem is the most fundament
theorem employed for analysis of interconnection networks.
At
final section in this chapter, we will introduce some fundamental principles we should conform to in the process of design of an interconnection
network by the language of graph theory.
|
