组合网络理论（英文版）
正版图书 真实库存欢迎选购 套装图书先联系再下单 套装图书请先咨询客服再下单
￥ 73.7 5.8折 ￥ 128 全新
仅1件
河北保定
认证卖家担保交易快速发货售后保障
作者徐俊明
出版社科学出版社
ISBN9787030364784
出版时间2013-04
装帧精装
开本16开
定价128元
货号7932030
上书时间2024-10-24
- 在售商品 暂无
- 平均发货时间 24小时
- 好评率 暂无
商品详情
- 品相描述：全新
- 商品描述
-
内容摘要
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
相关推荐
— 没有更多了 —
以下为对购买帮助不大的评价