Applied Graph Theory. An Introduction with Graph Optimization and Algebraic Graph Theory

✍ Scribed by Cristofer Griffin

• Publisher: World Scientific Publishing
• Year: 2023
• Tongue: English
• Leaves: 305
• Category: Library

✦ 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