Preface
Chapter 1 Basic Concepts of Graphs
1.1 Graph and Graphical Representation
1.2 Graph Isomorphism
1.3 Vertex Degrees
1.4 Subgraphs and Operations
1.5 Walks， Paths and Connection
Chapter 2 Advanced Concepts of Graphs
2.1 Distances and Diameters
2.2 Circuits and Cycles
2.3 Eulerian Graphs
2.4 Hamiltonian Graphs
2.5 Matrix Representations of Graphs
2.6 Exponents of Primitive Matrices
Chapter 3 Trees and Graphic Spaces
3.1 Trees and Spanning Trees
3.2 Vector Spaces of Graphs
3.3 Enumeration of Spanning Trees
3.4 The Minimum Connector Problem
3.5 The Shortest Path Problem
3.6 The Electrical Network Equations
Chapter 4 Plane Graphs and Planar Graphs
4.1 Plane Graphs and Euler’s Formula
4.2 Kuratowski’s Theorem
4.3 Dual Graphs
4.4 Regular Polyhedra
4.5 Layout of Printed Circuits
Chapter 5 Flows and Connectivity
5.1 Network Flows
5.2 Menger’s Theorem
5.3 Connectivity
5.4 Design of Transport Schemes
5.5 Design of Optimal Transport Schemes
5.6 The Chinese Postman Problem
5.7 Construction of Squared Rectangles
Chapter 6 Matchings and Independent Sets
6.1 Matchings
6.2 Independent Sets
6.3 The Personnel Assignment Problem
6.4 The Optimal Assignment Problem
6.5 The Travelling Salesman Problem
Chapter 7 Colorings and Integer Flows
7.1 Vertex-Colorings
7.2 Edge-Colorings
7.3 Face-Coloring and Four-Color Problem
7.4 Integer Flows and Cycle Covers
Chapter 8 Graphs and Groups
8.1 Group Representation of Graphs
8.2 Transitive Graphs
8.3 Graphic Representation of Groups
8.4 Design of Interconnection Networks
Bibliography
List of Notations
Index
內容試閱：
Chapter 1
Basic Concepts of Graphs
In many real-world situations， it is particularly convenient to describe the specified relationship between pairs of certain given objects by means of a diagram， in which points represent the objects and directed or undirected lines represent the relationship between pairs of the objects. For xample， a national traffic map describes a condition of the communication lines among cities in the country， where the points represent cities and the lines represent the highways or the railways oining pairs of cities. Notice that in such diagrams one is mainly interested in whether or not two
given points are joined by a line; the manner in which they are joined is immaterial. A mathematical abstraction of situations of this type gives rise to the concept of a graph.
In fact， a graph provides the natural structures from which to construct mathematical models that are appropriate to almost all fields of scientific natural and social inquiry. The underlying subject f study in these fields is some set of “objects” and one or more “relations” between the objects.
In this chapter， we will introduce the concept and the geometric representation of a graph， erminology and natation， basic operations used in the remaining parts of the book. It should， for the beginner specially， be worth noting that most graph theorists use personalized terminology in their books， papers and lectures. Even the meaning of the word “graph” varies with different authors. We will adopt the most standard terminology and notation extensively used by most authors， such as Bondy
and Murty1 [42]， with a subject index and a list of notations in the end of the book.
1 J. A. Bondy John Adrian Bondy is a professor of University of Waterloo and Universit′e Lyon 1， received his Ph.D. from University of Oxford in 1969. U. S. R. Murty Uppaluri Siva Ramachandra Murty is a professor of University of Waterloo， received his Ph.D. from Indian Statistical Institute in 1967. Bondy and Murty served as editors-in-chief of Journal of Combinatorial Theory， Series B 1985-2004， see this journal， 2004， 901:1. They are well known and respected for many contributions to graph theory. Particularly， their joint textbook Graph Theory with Applications [42] is acclaimed by readers. The book’s clear exposition and careful choice of topics made it widely influential， and for many years it was used as the principal reference for graph theory courses around the world. It is this textbook that plays an important role to standardize the terminology and notation of graphs. In 2008， they published the new book Graph Theory [43].
1.1 Graph and Graphical Representation
Let V be a non-empty set. An ordered pair x， y or an unorder pair xy is often used to denote a binary relation between two elements in V ， where x， y denotes a unilateral relation from x to y and xy denotes a bilateral relation between x and y. A set of binary relations on V can be denoted as a subset of V × V ， the Cartesian product of V with itself. Mathematically， a graph1 G is a mathematical structure V，E， denoted by G = V，E， where E V × V
Example 1.1.1 D = V D，ED is a graph， where
V D = {x1， x2， x3， x4， x5} and
ED = {a1， a2， a3， a4， a5， a6， a7， a8}，
and for each i = 1， 2， ， 8， ai is a unilateral relation defined by
a1 = x1， x2， a2 = x3， x2， a3 = x3， x3， a4 = x4， x3，
a5 = x4， x2， a6 = x5， x2， a7 = x2， x5， a8 = x3， x5.
Example 1.1.2 H = V H，EH is a graph， where
V H = {y1， y2， y3， y4， y5} and
EH = {b1， b2， b3， b4， b5， b6， b7， b8}，
and for each i = 1， 2， ， 8， bi is a unilateral relation defined by
b1 = y1， y2， b2 = y3， y2， b3 = y3， y3， b4 = y4， y3，
b5 = y4， y2， b6 = y5， y2， b7 = y2， y5， b8 = y3， y5.
Example 1.1.3 G = V G，EG is a graph， where
V G = {z1， z2， z3， z4， z5， z6} and
EG = {e1， e2， e3， e4， e5， e6， e7， e8， e9}，
and for each i = 1， 2， ， 9， ei is a bilateral relation defined by
e1 = z1z2， e2 = z1z4， e3 = z1z6， e4 = z2z3， e5 = z3z4，
e6 = z3z6， e7 = z2z5， e8 = z4z5， e9 = z5z6.
A graph G = V，E can be drawn on the plane. Each element in V is indicated by a point. For clarity， such a point is often depicted as a small circle. For an
1 The word “graph” was first used in this sense by J. J. Sylvester James Joseph Sylvester， 1814-1897 in 1878 Chemistry and algebra. Nature， 1877-8， 17: 284. Sylvester was an English mathematician， played a leadership role in American mathematics in the later half of the 19th century as a professor at the Johns Hopkins University and as founder of the American Journal of Mathematics.
element e in E， if e = x， y， we draw a directed line segment or curve joining two points from x to y; if e = xy， we draw an undirected line segment or curve joining two points x and y. Such a geometric diagram is called a graphical representation or geometric representation of the graph， which intuitively shows the configuration of the graph. Clearly， graphical repre
購物車/收銀台(
0
) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
