Graph Theory

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0007.djvu
Preface......Page __sk_0005.djvu
1.1 Fundamental Concepts and Notation......Page __sk_0011.djvu
1.2 Elementary Properties and Operations......Page __sk_0018.djvu
1.3 Alternate Representations for Graphs......Page __sk_0023.djvu
1.4 Algorithms......Page __sk_0025.djvu
1.5 Degree Sequences......Page __sk_0028.djvu
1.6 Fundamental Counting......Page __sk_0034.djvu
2.1 Distance......Page __sk_0041.djvu
2.2 Connectivity......Page __sk_0053.djvu
2.3 Digraph Connectivity......Page __sk_0061.djvu
2.4 Problem Solving and Heuristics......Page __sk_0065.djvu
3.1 Fundamental Properties of Trees......Page __sk_0075.djvu
3.2 Minimal Weight Spanning Trees......Page __sk_0078.djvu
3.3 Counting Trees......Page __sk_0082.djvu
3.4 Directed Trees......Page __sk_0086.djvu
3.5 Optimal Directed Subgraphs......Page __sk_0091.djvu
3.6 Binary Trees......Page __sk_0095.djvu
3.7 More About Counting — Using Generating Functions......Page __sk_0103.djvu
4.1 Flows......Page __sk_0109.djvu
4.2 The Ford and Fulkerson Approach......Page __sk_0111.djvu
4.3 The Dinic Algorithm and Layered Networks......Page __sk_0118.djvu
4.4 Layered Networks and Potential......Page __sk_0122.djvu
4.5 Variations on Networks......Page __sk_0123.djvu
4.6 Connectivity and Networks......Page __sk_0128.djvu
5.1 Eulerian Graphs......Page __sk_0135.djvu
5.2 Adjacency Conditions for Hamiltonian Graphs......Page __sk_0141.djvu
5.3 Related Hamiltonian-like Properties......Page __sk_0149.djvu
5.4 Hamiltonian Digraphs......Page __sk_0152.djvu
5.5 Other Types of Hamiltonian Results......Page __sk_0154.djvu
5.6 The Traveling Salesman Problem......Page __sk_0157.djvu
5.7 Short Cycles and Girth......Page __sk_0159.djvu
6.1 Euler's Formula......Page __sk_0169.djvu
6.2 Characterizations of Planar Graphs......Page __sk_0173.djvu
6.3 A Planarity Algorithm......Page __sk_0183.djvu
6.4 The Hopcroft-Tarjan Planarity Algorithm......Page __sk_0187.djvu
6.5 Hamiltonian Planar Graphs......Page __sk_0195.djvu
7.1 Matchings and Bipartite Graphs......Page __sk_0201.djvu
7.2 Matching Algorithms and Marriage......Page __sk_0208.djvu
7.3 Factoring......Page __sk_0221.djvu
8.1 Vertex Independence and Coverings......Page __sk_0231.djvu
8.2 Vertex Colorings......Page __sk_0233.djvu
8.3 Approximate Coloring Algorithms......Page __sk_0239.djvu
8.4 Edge Colorings......Page __sk_0246.djvu
8.5 The Four Color Theorem......Page __sk_0249.djvu
8.6 Chromatic Polynomials......Page __sk_0251.djvu
8.7 Perfect Graphs......Page __sk_0254.djvu
9.1 Graphs and Ordered Sets......Page __sk_0261.djvu
9.2 Isomorphism......Page __sk_0267.djvu
9.3 Ramsey Theory......Page __sk_0277.djvu
9.4 Finite State Machines......Page __sk_0283.djvu
9.5 Scheduling......Page __sk_0288.djvu
9.6 Tournaments......Page __sk_0294.djvu
10.0 Introduction......Page __sk_0307.djvu
10.1 Complete Subgraphs......Page __sk_0308.djvu
10.2 Cycles in Graphs......Page __sk_0312.djvu
10.3 On the Structure of Extremal Graphs......Page __sk_0318.djvu
10.4 Other Directions — Random Graphs......Page __sk_0324.djvu
Appendix......Page __sk_0333.djvu
Index......Page __sk_0335.djvu