Applied Graph Theory: An Introduction With Graph Optimization And Algebraic Graph Theory

✍ Scribed by Christopher H Griffin

• Publisher: WSPC
• Year: 2023
• Tongue: English
• Leaves: 305
• Category: Library

✦ Synopsis

This book serves as an introduction to graph theory and its applications. It is intended for a senior undergraduate course in graph theory but is also appropriate for beginning graduate students in science or engineering. The book presents a rigorous (proof-based) introduction to graph theory while also discussing applications of the results for solving real-world problems of interest. The book is divided into four parts. Part 1 covers the combinatorial aspects of graph theory including a discussion of common vocabulary, a discussion of vertex and edge cuts, Eulerian tours, Hamiltonian paths and a characterization of trees. This leads to Part 2, which discusses common combinatorial optimization problems. Spanning trees, shortest path problems and matroids are all discussed, as are maximum flow problems. Part 2 ends with a discussion of graph coloring and a proof of the NP-completeness of the coloring problem. Part 3 introduces the reader to algebraic graph theory, and focuses on Markov chains, centrality computation (e.g., eigenvector centrality and page rank), as well as spectral graph clustering and the graph Laplacian. Part 4 contains additional material on linear programming, which is used to provide an alternative analysis of the maximum flow problem. Two appendices containing prerequisite material on linear algebra and probability theory are also provided.

✦ Table of Contents

Contents
About the Author
Preface
Acknowledgments
Part 1: Introduction to Graphs
1. Introduction to Graph Theory
1.1 Graphs, Multigraphs, and Simple Graphs
1.2 Directed Graphs
1.3 Chapter Notes
1.4 Exercises
2. Degree Sequences and Subgraphs
2.1 Degree Sequences
2.2 Some Types of Graphs from Degree Sequences
2.3 Subgraphs
2.4 Cliques, Independent Sets, Complements, and Covers
2.5 Chapter Notes
2.6 Exercises
3. Walks, Cycles, Cuts, and Centrality
3.1 Paths, Walks, and Cycles
3.2 More Graph Properties: Diameter, Radius, Circumference, and Girth
3.3 Graph Components
3.4 Introduction to Centrality
3.5 Chapter Notes
3.6 Exercises
4. Bipartite, Acyclic, and Eulerian Graphs
4.1 Bipartite Graphs
4.2 Acyclic Graphs and Trees
4.3 Eulerian Graphs
4.4 Chapter Notes
4.5 Exercises
Part 2: Optimization in Graphs and NP-Completeness
5. Trees, Algorithms, and Matroids
5.1 Two-Tree Search Algorithms
5.2 Building a BFS/DFS Spanning Tree
5.3 Prim’s Spanning Tree Algorithm
5.4 Computational Complexity of Prim’s Algorithm
5.5 Kruskal’s Algorithm
5.6 Shortest Path Problem in a Positively Weighted Graph
5.7 Floyd–Warshall Algorithm
5.8 Greedy Algorithms and Matroids
5.9 Chapter Notes
5.10 Exercises
6. An Introduction to Network Flows and Combinatorial Optimization
6.1 The Maximum Flow Problem
6.2 Cuts
6.3 The Max-Flow/Min-Cut Theorem
6.4 An Algorithm for Finding Optimal Flow
6.5 Applications of the Max-Flow/Min-Cut Theorem
6.6 More Applications of the Max-Flow/Min-Cut Theorem
6.7 Chapter Notes
6.8 Exercises
7. Coloring
7.1 Vertex Coloring of Graphs
7.2 Some Elementary Logic and NP-Completeness
7.3 NP-Completeness of k-Coloring
7.4 Graph Sizes and k-Colorability
7.5 Chapter Notes
7.6 Exercises
Part 3: Some Algebraic Graph Theory
8. Algebraic Graph Theory with Abstract Algebra
8.1 Isomorphism and Automorphism
8.2 Graph Isomorphism
8.3 Groups
8.4 Permutation Groups and Graph Automorphisms
8.5 Chapter Notes
8.6 Exercises
9. Algebraic Graph Theory with Linear Algebra
9.1 Matrix Representations of Graphs
9.2 Properties of the Eigenvalues of the Adjacency Matrix
9.3 Chapter Notes
9.4 Exercises
10. Applications of Algebraic Graph Theory
10.1 Eigenvector Centrality
10.2 Markov Chains and Random Walks
10.3 PageRank
10.4 The Graph Laplacian
10.5 Chapter Notes
10.6 Exercises
Part 4: Linear Programming and Graph Theory
11. A Brief Introduction to Linear Programming
11.1 Introduction and Rationale
11.2 Linear Programming: Notation
11.3 Intuitive Solutions to Linear Programming Problems
11.4 Some Basic Facts about Linear Programming Problems
11.5 Solving Linear Programming Problems with a Computer
11.6 Karush–Kuhn–Tucker Conditions
11.7 Duality
11.8 Chapter Notes
11.9 Exercises
12. Max Flow/Min Cut with Linear Programming
12.1 The Maximum Flow Problem as a Linear Program
12.2 The Dual of the Flow Maximization Problem
12.3 The Max-Flow/Min-Cut Theorem
12.4 Min-Cost Flow and Other Problems
12.5 The Problem of Generalizing König’s Theorem and Duality
12.6 Chapter Notes
12.7 Exercises
Appendix A. Fields, Vector Spaces, and Matrices
A.1 Matrices and Row and Column Vectors
A.2 Matrix Multiplication
A.3 Special Matrices
A.4 Matrix Inverse
A.5 Linear Combinations, Span, and Linear Independence
A.6 Basis
A.7 Orthogonality in Rn
A.8 Row Space and Null Space
A.9 Determinant
A.10 Eigenvalues and Eigenvectors
A.11 Exercises
Appendix B. A Brief Introduction to Probability Theory
B.1 Probability
B.2 Random Variables and Expected Values
B.3 Conditional Probability
B.4 Exercises
References
Index