| 內容介紹 | |
出版社：科學出版社 ISBN：9787030364784 商品編碼：10027149245034 包裝：精裝 開本：16開 出版時間：2013-04-01 頁數：420 代碼：128
"| 商品基本信息，請以下列介紹為準 | | 商品名稱： | 組合網絡理論-26 | | 作者： | | | 代碼： | 128.0 | | 出版社： | 科學出版社 | | 出版日期： | 2013-04-01 | | ISBN： | 9787030364784 | | 印次： | | | 版次： | 01 | | 裝幀： | 精裝 | | 開本： | 16開 |
| 摘要 | Chapter 1
Fundamentals of Networks and Graphr> In this chapter,we will briefly recall some basic concepts and notations on graph
theory used in thiook as well as the corresponding backgrounds in networkr> 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 Networkr> 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 oney another. In order to avoid quibbling it is necessary to present
a formidable number of definitionr> A graph G is an ordered pair (V,E),where both V and E are non-empty setr> 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) ir> called a directed graph,or digraph for short. For an edge e of a digraph G,sometimer> 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 loopr> Usually,it is convenient to denote an unordered pair of verticey xy or yx instead
of {x,y}. Edges of an undirected graph are sometimes called undirected edger> 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 edger> Two graphs G and H are isomorphic,denoted by G ~= H,if there exists a
&nbijective 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 isomorphietween 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 thiook 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 thor> performed by its components and by the manner in which the components are interconnected.
For a computer system,its components might include processors,control unitr> storage units and I/O (input/output) equipments (maybe include switches),and itr> function is to transform a set of input information items (e.g.,a program and itr> 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 computerr> 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
&nbetween the computers in the execution of programr> 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 numerour> &nbut the essential feature here is the switching network. The main advantage of thir> type of configuration is that it enables us to make the data access transparent to
the user who may regard data aeing held in a large memory which is readily
accele to any processor. However,this type of memory-sharing architecturer> can not easily take advantage of some inherent properties in problems,for example,
proximity of data where communication is local. Moreover,the switching network
&nbecomes exceedingly complex to build as the number of processors increaser> 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 enle 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 components of the network and whose edges represent physical
communication links,where directed edges represent one-way communication
links and undirected edges represent two-way communication links. Such a graph ir> called the topological structure of the interconnection network,or network topology
for short.
For example,a network based on Kn as its topological structure is often called a
fully connected network. Bipartite graphs are often used to model croar switcher> in the first class of MPS architectures. For example,Figure 1.4 shows a 3 × 3
croar switch and its topological structure K3,3.
Conversely,any a graph can ale considered as a topological structure of some
interconnection network. Topologically,graphs and interconnection networks are the
same things. Thus we will confuse a graph with a network. Instead of spe a
network,components,and links we speak of a graph,vertices and edges. The graph
is directed or undirected,depending upon that the links are one-way or two-way in
the network.
Usually the network topologies can be grouped into two categories: dynamic and
static. In a dynamic system such as the first class of MPS’s mentioned above the
links can be reconfigured by setting the network’s active switching elements. In a
static system such as the second class of MPS’s the communication linketween
processors are passive and reconfiguration of the system is not pole. In thir> &nbook,we are mainly interested in a static topological structure of interconnection
networkr> 1.2 Basic Concepts and Notationr> In this section,we will give some basic terminologies,notations and results on graphr> used in thiook,including graphs,degrees,paths,cycles,connected graphs,Euler
circuits,Hamilton cycles,adjacency matrices,matchings,independence numberr> dominating numbers,and so forth.
A graph is one of the moasic concepts in graph theory. We first recall
various graphs induced by operations of graphr> Suppose that G = (V,E) is a graph. A graph H is called a graph of G,denoted
&nby H ? G,if V (H) ? V (G) and E(H) ? E(G). A graph H of G is called a
spanning graph if V (H) = V (G).
The complement Gc of a graph G is the graph with the vertex-set V ,and (x,y) ∈
E(Gc) ? (x,y) /∈ E(G).
Let S be a non-empty set of V (G). The induced graph by S,denoted by
G[S],is a graph of G whose vertex-set is S and whose edge-set is the set of thor> edges of G that have both end-vertices in S. The ol G?S denotes the induced
graph G[V \\ S].
Let B be a non-empty set of E(G). The edge-induced graph by B,denoted
&nby G[B],is a graph of G whose vertex-set is the set of end-vertices of edges in
B and whose edge-set is B. The notation G ? B denotes a graph of G obtained
&nby deleting all edges in B. Similarly,the graph obtained from G by ing a set of
edges F is denoted by G + F,where F ? E(Gc).
Subgraphs may be used to model a network of an interconnection network.
If G is the topological structure of an interconnection network,then G + F meanr> ition of a set of links F to the network to improve its performance;G ? S and
G ? B mean that the network contains a set S of faulty processors and a set B of
faulty links,respectively.
It is essential that an interconnection network should contain some given kinds of
networks. It iecause that for a computing system its function is the execution
of some algorithmr> Following Hayes [213],an algorithm may be modeled by a graph whose verticer> represent the facilities required to execute the algorithm,and whose edges represent
the links required among these facilities. Such a graph is called a communication
pattern of the algorithm. Thus,an algorithm is executable by a computing system
G if and only if its communication pattern is isomorphic to a graph of G.
Let G1 and G2 be graphs of G. We say that G1 and G2 are disjoint if they
have no vertices in common,and edge-disjoint if they have no edges in common.
The union G1 ∪ G2 of G1 and G2 is the graph with vertex-set V (G1) ∪ V (G2)
and edge-set E(G1) ∪E(G2);if G1 and G2 are disjoint,we sometimes denoted their
union by G1 + G2. The intersection G1 ∩ G2 of G1 and G2 is defined similarly if
V (G1) ∩ V (G2) = ?.
The join G ∨ H of two disjoint undirected graphs G and H is the undirected
graph obtained from G + H by joining each vertex of G to each vertex of H.
We now recall the concepts related to degrees of a graph. We first consider
undirected graphs. Let G be an undirected graph and x ∈ V (G). We use the
notation EG(x) to denote a set of edges incident with x in G. The cardinality
|EG(x)| is called the degree of x,denoted by dG(x).
When an interconnection network is modeled by a graph G,the degree dG(x) of
a vertex x in G corresponds the number of available connections to the component
x in the network,which iounded by the number of I/O devices attached to the
component.
A vertex of degree d is called a d-degree vertex. 0-degree vertex is called an
isolated vertex. A vertex is called to be or even if its degree is or even.
A graph G is d-regular if dG(x) = d for each x ∈ V (G),and G is regular if it ir> d-regular for some d,and d is the regularity of G. A graph G is quasi-regular if there
are two distinct integers a and b such that dG(x) = a or b for any x ∈ V (G). The
parameterr> Δ(G) = max{dG(x) : x ∈ V (G)},and
δ(G) =min{dG(x) : x ∈ V (G)}
are the maximum and minimum degree of G,respectively. For xy ∈ E(G),the |
" | | |
|
