作者：徐俊明
页数：457
出版社：科学出版社
出版日期：2015
ISBN：9787030438638
电子书格式：pdf/epub/txt
内容简介
本书着眼于有向图，将无向图作为特例，在一定的深度和广度上系统地阐述了图论的基本概念、理论和方法以及基本应用．全书内容共分７章，包括Euler回与Hamilton圈、树与图空间、平面图、网络流与连通度、匹配与独立集、染色理论、图与群以及图在矩阵论、组合数学、组合优化、运筹学、线性规划、电子学以及通讯和计算机科学等多方面的应用．每章分为理论和应用两部分，章末有小结和参考文献．各章内容之间联系紧密，许多著名的定理给出最新最简单的多种证明．每小节末有大量习题，书末附有记号和名词索引．
目录
contents
preface iii
chapter 1 basic concepts of graphs 1
1.1 graph and graphical representation.2
1.2 graph isomorphism.10
1.3 vertex degrees 20
1.4 subgraphs and operations 32
1.5 walks， paths and connection 44
chapter 2 advanced concepts of graphs 53
2.1 distances and diameters53
2.2 circuits and cycles 66
2.3 eulerian graphs 79
2.4 hamiltonian graphs 88
2.5 matrix representations of graphs 103
2.6 exponents of primitive matrices 115
chapter 3 trees and graphic spaces 125
3.1 trees and spanning trees.125
3.2 vector spaces of graphs 143
3.3 enumeration of spanning trees 157
3.4 the minimum connector problem. 166
3.5 the shortest path problem.173
3.6 the electrical network equations 182
chapter 4 plane graphs and planar graphs 187
4.1 plane graphs and euler’s formula187
4.2 kuratowski’s theorem.200
4.3 dual graphs.209
4.4 regular polyhedra.214
4.5 layout of printed circuits 217
chapter 5 flows and connectivity.225
5.1 network flows 225
5.2 menger’s theorem.230
5.3 connectivity.244
5.4 design of transport schemes 260
5.5 design of optimal transport schemes 268
5.6 the chinese postman problem 273
5.7 construction of squared rectangles.280
chapter 6 matchings and independent sets 287
6.1 matchings 287
6.2 independent sets 302
6.3 the personnel assignment problem.310
6.4 the optimal assignment problem. 319
6.5 the travelling salesman problem.327
chapter 7 colorings and integer flows 336
7.1 vertex-colorings.336
7.2 edge-colorings 348
7.3 face-coloring and four-color problem.356
7.4 integer flows and cycle covers368
chapter 8 graphs and groups 383
8.1 group representation of graphs383
8.2 transitive graphs 389
8.3 graphic representation of groups 400
8.4 design of interconnection networks 409
bibliography 421
list of notations 440
index 444
preface iii
chapter 1 basic concepts of graphs 1
1.1 graph and graphical representation.2
1.2 graph isomorphism.10
1.3 vertex degrees 20
1.4 subgraphs and operations 32
1.5 walks， paths and connection 44
chapter 2 advanced concepts of graphs 53
2.1 distances and diameters53
2.2 circuits and cycles 66
2.3 eulerian graphs 79
2.4 hamiltonian graphs 88
2.5 matrix representations of graphs 103
2.6 exponents of primitive matrices 115
chapter 3 trees and graphic spaces 125
3.1 trees and spanning trees.125
3.2 vector spaces of graphs 143
3.3 enumeration of spanning trees 157
3.4 the minimum connector problem. 166
3.5 the shortest path problem.173
3.6 the electrical network equations 182
chapter 4 plane graphs and planar graphs 187
4.1 plane graphs and euler’s formula187
4.2 kuratowski’s theorem.200
4.3 dual graphs.209
4.4 regular polyhedra.214
4.5 layout of printed circuits 217
chapter 5 flows and connectivity.225
5.1 network flows 225
5.2 menger’s theorem.230
5.3 connectivity.244
5.4 design of transport schemes 260
5.5 design of optimal transport schemes 268
5.6 the chinese postman problem 273
5.7 construction of squared rectangles.280
chapter 6 matchings and independent sets 287
6.1 matchings 287
6.2 independent sets 302
6.3 the personnel assignment problem.310
6.4 the optimal assignment problem. 319
6.5 the travelling salesman problem.327
chapter 7 colorings and integer flows 336
7.1 vertex-colorings.336
7.2 edge-colorings 348
7.3 face-coloring and four-color problem.356
7.4 integer flows and cycle covers368
chapter 8 graphs and groups 383
8.1 group representation of graphs383
8.2 transitive graphs 389
8.3 graphic representation of groups 400
8.4 design of interconnection networks 409
bibliography 421
list of notations 440
index 444
