Graphs
From charlesreid1
Graphs are mathematical objects consisting of vertices and edges.
The original inventor of graph theory was (arguably) Leonhard Euler, who used it to solve the Seven Bridges of Königsberg problem.
Notes
Goodrich - Data Structures - Chapter 12
The Goodrich book is less extensive, less mathematical, and more practical. The focus is on graph implementations, not on graph theory.
Data Structures
Goodrich begins Chapter 12 by covering data structures common in storing graphs: Graphs/Data Structures
- Edge list (two linked lists, one for vertices, one for edges)
- Adjacency list (one linked list for vertices, storing references to edges)
- Adjacency map (map that stores vertices as keys, other vertices and the edge that links them to the key vertex as values)
- Adjacency matrix (N x N matrix, where N is number of vertices, with entry (i,j) indicating an edge connecting vertex i to vertex j)
Graph Traversals
This is arguably the most important graph algorithm, as many, many graph algorithms are based on the traversal procedure.
Depth first search and traversals on graphs: Graphs/Depth First Traversal
Breadth first search and traversals on graphs: Graphs/Breadth First Traversal
Euler tours on graphs: Graphs/Euler Tour
Transitive Closure
Transitive closure graphs: Graphs/Transitive Closure
Floyd Warshall algorithm: Graphs/Floyd Warshall
Directed Acyclic Graphs
Directed acyclic graphs are graphs that are both directed and that do not contain cycle.
Detecting cycles: Graphs/Cycles
Directed acyclic graphs: Graphs/DAGs
Topographical sort of directed acyclic graphs: Graphs/Topological Sort
Shortest Paths
Dijkstra's algorithm:
Minimum Spanning Trees
Minimum spanning trees:
Diestel - Graph Theory
Link to book: https://diestel-graph-theory.com/
Chapter 1: The Basics
Chapter 1 is a litany of definitions, concepts, and theorems important to laying the groundwork for discussing graph theory.
Chapter 2: Matching, Covering and Packing
Chapter 2 introduces wave after wave of new terms and notation, and is a bit hard to follow. It covers the concept of finding a set of edges that can connect all vertices between two subsets of vertices on a graph.
Chapter 3: Connectivity
Chapter 3 covers k-connectedness on graphs. Being k-connected means any two of its vertices can be joined by k independent paths.
Chapter 4: Planar Graphs
Chapter 4 covers planar graphs — graphs that can be drawn in the plane without edge crossings. Includes Kuratowski's theorem and the Four Colour Theorem context.
Chapter 5: Colouring
Chapter 5 covers vertex and edge colouring of graphs, including the chromatic number, the Four Colour Theorem, and colouring algorithms.
Chapter 6: Flows
Chapter 6 covers network flows and circulations, including the max-flow min-cut theorem and its applications to connectivity and matching.
Chapter 7: Extremal Graph Theory
Chapter 7 covers extremal graph theory: given a graph property, what is the maximum (or minimum) number of edges a graph on n vertices can have while satisfying (or avoiding) that property?
Chapter 8: Infinite Graphs
Chapter 8 extends graph theory concepts to infinite graphs, covering ends, rays, and generalisations of connectivity and matching to infinite settings.
Chapter 9: Ramsey Theory for Graphs
Chapter 9 covers Ramsey theory: the phenomenon that complete disorder is impossible — any sufficiently large graph (or colouring of its edges) contains a highly structured substructure.
Chapter 10: Hamilton Cycles
Chapter 10 covers Hamilton cycles: cycles that visit every vertex exactly once. Includes necessary and sufficient conditions for Hamiltonicity.
Chapter 11: Random Graphs
Chapter 11 covers random graphs, especially the Erdős–Rényi model G(n,p), threshold functions, and the probabilistic method.
Chapter 12: Minors, Trees and WQO
Chapter 12 covers graph minors, tree-decompositions, and well-quasi-ordering — culminating in the Graph Minor Theorem (formerly Wagner's conjecture).
Flags
