Graph Theory = Optimization among all solutions that satisfy structural constraints.
I. Connectivity
Connected Graph
A graph in which there exists a path between any two vertices.
Connected Component
A maximal connected subgraph.
Strongly Connected Graph (Directed Graph)
A graph in which any two vertices are mutually reachable.
Strongly Connected Component (SCC)
A maximal strongly connected subgraph.
Articulation Point
A vertex whose removal increases the number of connected components.
Bridge
An edge whose removal increases the number of connected components.
II. Spanning Trees
Spanning Tree
A connected acyclic subgraph that includes all vertices and has $n-1$ edges.
Minimum Spanning Tree (MST)
The spanning tree with the minimum edge weight sum among all spanning trees.
Strict Second Best Spanning Tree
The smallest spanning tree among those with weights greater than MST.
Non-Strict Second Best Spanning Tree
The spanning tree with the minimum weight that is different from MST.
III. Path Problems
Path
A sequence of edges with no repeated vertices.
Shortest Path
The path with the minimum length among all $s o t$ paths.
Shortest Path Tree
A tree formed by the shortest paths originating from a source vertex.
$k$-th Shortest Path
The $k$-th smallest path when sorted by path length.
IV. Matching
Matching
A set of edges with no shared endpoints.
Maximum Matching
The matching with the maximum number of edges among all matchings.
Perfect Matching
A matching in which every vertex is matched.
Maximum Matching in Bipartite Graphs
The matching with the most edges in a bipartite graph.
V. Network Flow
Flow
An edge weight distribution that satisfies capacity constraints and flow conservation.
Maximum Flow
The flow with the maximum total flow among all feasible flows.
Cut
A partition of the vertex set that separates $s$ and $t$.
Minimum Cut
The cut with the minimum capacity among all $s,t$ cuts.
Minimum Cost Maximum Flow
The flow with the minimum cost under the constraint of maximum flow.
VI. Eulerian and Hamiltonian
Eulerian Path
A path that visits every edge exactly once.
Eulerian Circuit
A circuit that visits every edge exactly once and returns to the starting point.
Hamiltonian Path
A path that visits every vertex exactly once.
Hamiltonian Circuit
A circuit that visits every vertex exactly once and returns to the starting point.
VII. Topological Structures
Topological Sorting
A linear ordering of the vertices of a DAG such that all edges point in the same direction.
DAG (Directed Acyclic Graph)
A directed graph with no directed cycles.
VIII. Tree Structures
Tree
A connected graph with no cycles.
Forest
A graph consisting of several trees.
Diameter (Tree)
The length of the longest simple path in the tree.
Centroid (Tree)
A vertex whose removal minimizes the size of the largest remaining subtree.
IX. Significance
Facilitates review.