图论导引

书籍目录

Preface

Chapter 1 Fundamental Concepts

1.1 What Is a Graph?

The Definition

Graphs as Models

Matrices and Ismorphism

Decomposition and Special Graphs

Exercises

1.2 Paths,Cycles,and Trails

Connection in Graphs

Bipartite Graphs

Exercises

1.3 Vertex Degrees and Counting

Counting and Bijections

Extremal Problems

Graphic Sequences

Excercises

1.4 Directed Graphs

Definitions and Examples

Vertex Degrees

Eulerian Digraphs

Orientations and Tournaments

Exercises

Chapter 2 Trees and Distance

2.1 Basic Properties

Properties of Trees

Distance in Trees and Graphs

Disjoint Spanning Trees(optional)

Exercises

2.2 Spanning Trees and Enumeration

Enumeration of Trees

Spanning Trees in Graphs

Decomposition and Graceful Labelings

Branchings and Eulerian Digraphs(optional)

2.3 Optimization and Trees

Minimum Spanning Tree

Shortese Paths

Trees in Computer Science(optional)

Exercises

Chapter 3 Matchings and Factors

3.1 Matchings and Covers

Maximum Matchings

Hall's Matching Condition

Min-Max Theorems

Independent Sets and Covers

Dominating Sets(optional)

Exercises

3.2 Algorithms and Applications

Maximum Bipartite Matching

Weighted Bipartite Matching

Stable Matchings(optional)

Faster Bipartite Matching(optional)

Exercises

3.3 Matchings in General Graphs

Tutt's 1-factor Hteorem

f-factors of Graphs(optional)

Edmonds'Blossom Algorithm(optional)

Exercises

……

作者简介

图论在计算科学、社会科学和自然科学等各个领域都有广泛应用。本书是本科生或研究生一学期或两学期的图论课程教材。全书力求保持按证明的难度和算法的复杂性循序渐进的风格，使学生能够深入理解书中的内容。书中包括对证明技巧的讨论、1200多道习题、400多幅插图以及许多例题，而且对所有定理都给出了详细完整的证明。虽然本书包括许多算法和应用，但是重点在于理解图论结构和分析图论问题的技巧。

图书封面

 图论导引下载