内容摘要 Chapter 1 Fundamentals of Networks and Graphs In this chapter,we will briefly recall some basic concepts and notations on graph theory used in this book as well as the corresponding backgrounds in 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, Bondy and Murty [59],Chartrand and Lesniak [83],or Xu [503]. 1.1 Graphs and Networks In this section,we will introduce some concepts on graphs as well as how to model an interconnection network by a graph. Although they have been contained in any standard text-book on graph theory,these concepts defined by one author are different from ones by another. In order to avoid quibbling it is necessary to present a formidable number of definitions. A graph G is an ordered pair (V,E),where both V and E are non-empty sets, V = V (G) is the vertex-set of G,elements in which are called vertices of G;E = E(G) ? V × V is the edge-set of G,elements in which are called edges of G. The number of vertices of G,also called order of G,is denoted by υ(G). The number of edges of G,also called size of G,is denoted by ε(G). Two vertices corresponding an edge are called the end-vertices of the edge. The edge whose end-vertices are identical is a loop. The end-vertices of an edge are said to be incident with the edge,and vice versa. Two vertices are said to be adjacent if they are two end-vertices of some edge;two edges are said to be adjacent if they have an end-vertex in common. If E ? V ×V is considered as a set of ordered pairs,then the graph G = (V,E) is called a directed graph,or digraph for short. For an edge e of a digraph G,sometimes, called a directed edge or arc,if a = (x,y) ∈ E(G),then vertices x and y are called the tail and the head of e,respectively;and e is called an out-going edge of x and an in-coming edge of y. If E ? V ×V is considered as a set of unordered pairs,then the graph G = (V,E) is called an undirected graph. Note that an undirected graph does not admit loops. Usually,it is convenient to denote an unordered pair of vertices by xy or yx instead of {x,y}. Edges of an undirected graph are sometimes called undirected edges. A graph G is empty if ε(G) = 0,denoted by Kcυ ,and non-empty otherwise. An undirected graph can be thought of as a particular digraph,a symmetric digraph, in which there are two directed edges called symmetric edges,one in each direction, corresponding to each undirected edge. Thus,to study structural properties of graphs for digraphs is more general than for undirected graphs. A digraph is said to be non-symmetric if it contains no symmetric edges. Two graphs G and H are isomorphic,denoted by G ~= H,if there exists a bijective mapping θ between V (G) and V (H) satisfying the adjacency-preserving condition: (x,y) ∈ E(G) ? (θ(x),θ(y)) ∈ E(H). The mapping θ is called an isomorphism between G and H. Up to isomorphism,there is just one complete graph of order n,denoted by Kn, and one complete bipartite graph G(X ∪ Y,E),denoted by Km,n if |X| = m and |Y | = n,where {X,Y } is a bipartition of V (G). It is customary to call K1,n a star. The graphs shown in Figure 1.1 are a complete undirected graph K5,a complete digraph K3 and a complete bipartite undirected graph K3,3,respectively. Throughout this book the letter G always denotes a graph,which is directed or undirected according to the context if it is not specially noted. A system,following Hayes [214],may be defined informally as a collection of objects,called components,connected to form a coherent entity with a well-defined function or purpose. The function performed by the system is determined by those performed by its components and by the manner in which the components are interconnected. For a computer system,its components might include processors,control units, storage units and I/O (input/output) equipments (maybe include switches),and its function is to transform a set of input information items (e.g.,a program and its data set) into output information (e.g.,the results computed by the program acting on the data set). A computer network is a system whose components are autonomous computers and other devices that are connected together usually over long physical distance. Each computer has its own operating system and there is no direct cooperation between the computers in the execution of programs. A multiple processor system (MPS) is a system whose components are two or more autonomous processors. Thus,an MPS may be thought of as an integrated computer system containing two or more processors. The qualification “integrated” implies that the processors cooperate in the execution of programs. MPS’s consisting of thousands of processors are capable of executing parallel algorithms thus solving large problems in real time. Following Saad and Schultz [401],there are essentially two broad classes of MPS architectures. The first class of MPS’s is that its n identical processors are interconnected via a large switching network to n memories. The diagram of such a class of MPS architectures is shown in Figure 1.2. Variations on this scheme are numerous, but the essential feature here is the switching network. The main advantage of this type of configuration is that it enables us to make the data access transparent to the user who may regard data as being held in a large memory which is readily accessible to any processor. However,this type of memory-sharing architectures can not easily take advantage of some inherent properties in problems,for example, proximity of data where communication is local. Moreover,the switching network becomes exceedingly complex to build as the number of processors increases. The second important class of MPS architecture is that its processors,in which each processor has its own local memory,are interconnected according to some convenient pattern. The diagram of such a class of MPS architectures is shown in Figure 1.3. In this type of machine,there are no shared memory and no global synchronization. Moreover,intercommunication is achieved by message passing and computation is data driven. The main advantage of such architectures,often referred to as ensemble architectures,is the simplicity of their design. The processors are identical,or are of a few different kinds,and can therefore be fabricated at relatively low cost. A basic feature for a system is that its components are connected together by physical communication links to transmit information according to some pattern. Moreover,it is undoubted that the power of a system is highly dependent upon the connection pattern of components in the system. A connection pattern of components in a system is called an interconnection network,or network for short,of the system. Topologically,an interconnection network can essentially depict structural feature of the system. In other words,an interconnection network of a system provides logically a specific way in which all components of the system are connected. It is quite natural that an interconnection network may be modeled by a graph whose vertices represent
以下为对购买帮助不大的评价