图论及其算法
出版时间：2012年版
丛编项： 中国矿业大学新世纪教材建设工程资助教材
内容简介
《中国矿业大学新世纪教材建设工程资助教材：图论及其算法》共分九章，主要内容包括图的基本概念、树、图的连通性、Euler环游和Hamilton回路、图的匹配、图的独立集和团、图的染色、平面图、网络流等。每章自成体系，不仅包含相关基础理论，还介绍了一些最新研究成果。另外，每章都穿插介绍了与章节内容紧密相关的若干算法等一些扩展阅读。《中国矿业大学新世纪教材建设工程资助教材：图论及其算法》注重理论与应用相结合，深入浅出，清晰易懂，并配有适当的例题和习题。《中国矿业大学新世纪教材建设工程资助教材：图论及其算法》主要使用英文编写，穿插部分中文，可用做普通高等学校数学、计算机科学、信息科学、管理科学等专业本科生的双语教学教材，也可供高校教师、图论研究人员参考使用。
目录
Chapter 1 Graphs and Subgraphs
1.1 Graphs and Their Representation
1.2 Constructing Graphs from Other Graphs
1.3 Directed Graphs
1.4 Infinite Graphs
1.5 Subgraphs and Supergraphs
1.6 Spanning and Induced Subgraphs
1.7 Modifying Graphs
1.8 Edge Cuts and Bonds
1.9 Even Subgraphs
1.10 最短路算法
1.11 Exercises
Chapter 2 Trees
2.1 Forests and Trees
2.2 Cut Edges
2.3 Spanning Trees
2.4 Cut Vertices
2.5 Tree-Search Alogrithms
2.6 Minimum-Weight Spanning Trees Alogrithm
2.7 最小权支撑树问题及应用
2.8 Exercises
Chapter 3 Connected Graphs
3.1 Walks and Connection
3.2 Separations and Blocks
3.3 Vertex Connectivity
3.4 The Fan Lemma
3.5 Edge Connectivity
3.6 Three-Connected Graphs
3.7 Connection in Digraphs
3.8 Construction of Reliable Communication Networks
3.9 算法及应用
3.10 Exercises
Chapter 4 Euler Tours and Hamilton Cycle
4.1 Euler Tours
4.2 Hamiltonian and Nonhamiltonian Graphs
4.3 Path and Cycle Exchanges
4.4 Related Reading
4.5 算法及应用
4.6 Exercises
Chapter 5 Matchings
5.1 Maximum Matehings
5.2 Matchings in Bipartite Graphs
5.3 Matchings in Arbitrary Graphs
5.4 Perfect Matchings and Factors
5.5 Matching Algorithms
5.6 匹配算法理论及应用
5.7 Exercises
Chapter 6 Stable Sets and Cliques
6.1 Stable Sets
6.2 Turan's Theorem
6.3 Ramsey's Theorem
6.4 Random Graphs
6.5 支配集、点独立集、点覆盖集的求法
6.6 Exercises
Chapter 7 Colorings
7.1 Chromatic Number
7.2 Critical Graphs
7.3 Girth and Chromatic Number
7.4 Perfect Graphs
7.5 List Colorings
7.6 Edge Chromatic Number
7.7 Vizing's Theorem
7.8 List Edge Colorings
7.9 Related Reading
7.10 图的点染色算法
7.11 Exercises
Chapter 8 Planar Graphs
8.1 Plane and Planar Graphs
8.2 Duality
8.3 Euler's Formula
8.4 Bridges
8.5 Kuratowski's Theorem
8.6 Colorings of Planar Maps
8.7 The Five-Color Theorem
8.8 Surface Embeddings of Graphs
8.9 Applications
8.10 Related Reading
8.11 不可平面图的几个研究方向简介
8.12 Exercises
Chapter 9 Flows in Networks
9.1 Transportation Network
9.2 The Max-Flow Min-Cut Theorem
9.3 Arc-Disjoint Directed Paths
9.4 网络最大流 Edmonds-Karp 算法
9.5 Exercises
参考文献
