Introduction to Graph Models
Graphs and Digraphs
Common Families of Graphs
Graph Modeling Applications
Walks and Distance
Paths, Cycles, and Trees
Vertex and Edge Attributes
Structure and Representation
Graph Isomorphism
Automorphism and Symmetry
Subgraphs
Some Graph Operations
Tests for Non-Isomorphism
Matrix Representation
More Graph Operations
Trees
Characterizations and Properties of Trees
Rooted Trees, Ordered Trees, and Binary Trees
Binary-Tree Traversals
Binary-Search Trees
Huffman Trees and Optimal Prefix Codes
Priority Trees
Counting Labeled Trees
Counting Binary Trees
Spanning Trees
Tree Growing
Depth-First and Breadth-First Search
Minimum Spanning Trees and Shortest Paths
Applications of Depth-First Search
Cycles, Edge-Cuts, and Spanning Trees
Graphs and Vector Spaces
Matroids and the Greedy Algorithm
Connectivity
Vertex and Edge-Connectivity
Constructing Reliable Networks
Max-Min Duality and Menger’s Theorems
Block Decompositions
Optimal Graph Traversals
Eulerian Trails and Tours
DeBruijn Sequences and Postman Problems
Hamiltonian Paths and Cycles
Gray Codes and Traveling Salesman Problems
Planarity and Kuratowski’s Theorem
Planar Drawings and Some Basic Surfaces
Subdivision and Homeomorphism
Extending Planar Drawings
Kuratowski’s Theorem
Algebraic Tests for Planairty
Planarity Algorithm
Crossing Numbers and Thickness
Graph Colorings
Vertex-Colorings
Map-Colorings
Edge-Colorings
Factorization
Special Digraph Models
Directed Paths and Mutual Reachability
Digraphs as Models for Relations
Tournaments
Project Scheduling
Finding the Strong Components of a Digraph
Network Flows and Applications
Flows and Cuts in Networks
Solving the Maximum-Flow Problem
Flows and Connectivity
Matchings, Transversals, and Vertex Covers
Graph Colorings and Symmetry
Automorphisms of Simple Graphs
Equivalence Classes of Colorings
Appendix