組合網(wǎng)絡(luò)理論

內(nèi)容概要

《組合網(wǎng)絡(luò)理論(英文版)》內(nèi)容簡介：This book provides the most basic combinatorial problems and well-established theory in design and analysis of the topological structure of interconnection networks in the graph-theoretic language.It covers the basic methods of network design，several well-known networks such as hypercubes，de Bruijn digraphs，Kautz digraphs，double loop，and the newest parameters to measure performance of networks such as forwarding indices of a routing，Menger number，Rabin number，fault-tolerant diameter，wide-diameter，generalized dominating number，and restricted connectivity.It will be of significant interest to researchers and practitioners working in design and analysis of networks，particularly to undergraduates and postgraduates specializing in computer science and applied mathematics.
Xu Junming is a Professor at School of Mathematical Sciences，the University of Science and Technology of China(USTC)，a fellow of Operations Research Society of China，and Commission on Combinatorics and Graph Theory in China.His research interest is combinatorics and graph theory，in particular，combinatorial problems of interconnection networks，has published more than 200 research papers.

書籍目錄

PrefacePart Ⅰ Networks and GraphsChapter 1 Fundamentals of Networks and Graphs1.1 Graphs and Networks1.2 Basic Concepts and Notations1.3 Trees and Planar Graphs1.4 Transmission Delay and Diameter1.5 Fault Tolerance and Connectivity1.6 Embedding and Routings1.7 Basic Principles of Network DesignExercisesChapter 2 Symmetry of Graphs or Networks2.1 Fundamentals on Groups2.2 Vertex-Transitive Graphs2.3 Edge-Transitive Graphs2.4 Atoms of Graphs2.5 Connectivity of Transitive GraphsExercisesPart Ⅱ Basic Methods of Network DesignsChapter 3 Line Graphical Methods3.1 Line Graphs and Basic Properties3.2 Basic Properties of Line Digraphs3.3 Iterated Line Graphs3.4 Connectivity of Line GraphsExercisesChapter 4 Cayley Methods4.1 Cayley Graphs4.2 Transitivity of Cayley Graphs4.3 Atoms and Connectivity of Cayley Graphs4.4 Vertex-Transitive Graphs with Prime OrderExercisesChapter 5 Cartesian Product Methods5.1 Cartesian Product of Graphs5.2 Diameter and Connectivity5.3 Other Properties of Cartesian Products5.4 Generalized Cartesian ProductsExercisesChapter 6 Basic Problems in Optimal Designs6.1 Undirected（d，k）-Graph Problems6.2 Directed（d，k）-Graph Problems6.3 Relations between Diameter and ConnectivityExercisesPart Ⅲ Well-Known Topologies of NetworksChapter 7 Hypercube Networks7.1 Definitions and Basic Properties7.2 Gray Codes and Cycles7.3 Lengths of Paths7.4 Embedding Problems7.5 Generalized Hypercubes7.6 Some Variations of HypercubesExercisesChapter 8 De Bruijn Networks8.1 Definitions and Basic Properties8.2 Uniqueness of Shortest Paths8.3 Generalized de Bruijn Digraphs8.4 Comparison with HypercubesExercisesChapter 9 Kautz Networks9.1 Definitions and Basic Properties9.2 Generalized Kautz Digraphs9.3 Connectivity of Generalized Kautz DigraphsExercisesChapter 10 Double Loop Networks10.1 Double Loop Networks10.2 L-Tiles in the Plane10.3 L-Tiles and Double Loop Networks10.4 Design of Optimal Double Loop Networks10.5 Basic Properties of Circulant NetworksExercisesChapter 11 Topologies of Other Networks11.1 Mesh Networks and Grid Networks11.2 Pyramid Networks11.3 Cube-Connected Cycles11.4 Butterfly Networks11.5 Bene* Networks11.6 Ω Networks11.7 Shuffle-Exchange NetworksExercisesPart Ⅳ Fault-Tolerant Analysis of NetworksChapter 12 Routings in Networks12.1 Forwarding Index of Routing12.2 Edge-Forwarding Index of Routing12.3 Forwarding Indices of Some Graphs12.4 Delay of Fault-Tolerant RoutingExercisesChapter 13 Fault-Tolerant Diameters in Networks13.1 Diameters of Altered Graphs13.2 Edge Fault-Tolerant Diameters13.3 Relations between Two Diameters13.4 Vertex Fault-Tolerant Diameters13.5 Fault-Tolerant Diameter of Product Graphs13.6 Fault-Tolerant Diameters of Some NetworksExercisesChapter 14 Menger-Type Problems in Parallel Systems14.1 Menger-Type Problems14.2 Bounded Menger Number and Connectivity14.3 Bounded Edge-Connectivity14.4 Rabin Numbers of NetworksExercisesChapter 15 Wide-Diameters of Networks15.1 Wide-Diameter and Basic Results15.2 Wide-Diameter of Regular Graphs15.3 Wide-Diameter of Cartesian Products15.4 Wide-Diameter and Independence Number15.5 Wide-Diameter and Fault-Tolerant Diameter15.6 Wide-Diameters of Some NetworksExercisesChapter 16 Generalized Independence and Domination Numbers16.1 Generalized Independence Numbers16.2 Generalized Domination Numbers16.3 Distance Independence and DominationExercisesChapter 17 Restricted Fault-Tolerance of Networks17.1 Restricted Connectivity and Diameter17.2 Restricted Edge-Connectivity17.3 Restricted Edge-Atoms17.4 Results on Transitive Graphs17.5 Super Connectivity of Networks17.6 Super Edge-Connectivity of Networks17.7 Super Connectivity of Line Graphs17.8 Connectivity Restricted by Degree-Conditions17.9 Connectivity Restricted by Order-Conditions17.10 Restricted Connectivity of Some NetworksExercisesBibliographyA List of NotationsIndex

章節(jié)摘錄

Chapter 1Fundamentals of Networks and GraphsIn 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 NetworksIn 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.

圖書封面

評論、評分、閱讀與下載

---

    組合網(wǎng)絡(luò)理論 PDF格式下載

---