Graphs represent pairwise connections; trees impose acyclicity.
Key knowledge
A finite graph has vertices V and edges between them; directed edges are ordered pairs. A nonempty simple undirected tree is connected and has no cycles; every pair of vertices has a unique simple path.
Conditions and scope
Simple graphs exclude loops and parallel edges in this entry.
A directed acyclic graph need not be an undirected tree.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
BFS finds shortest paths measured by number of edges in an unweighted graph. Dijkstra's algorithm computes single-source minimum-weight distances when every edge weight is nonnegative, repeatedly settling the smallest tentative distance.
An AVL binary search tree maintains subtree heights differing by at most one at every node. Its height is O(log n); search and updates with local rotations and maintained heights take O(log n) worst-case time.
A binary max heap stores a complete binary tree in an array with every parent key at least its children's keys. Maximum lookup is O(1); upward/downward restoration after insertion or extraction costs O(log n), and bottom-up heap construction costs O(n).
Dynamic programming states subproblems and recurrences, checks an acyclic dependency order and base cases, and evaluates each needed subproblem once by memoization or bottom-up order. Total work sums the nonrecursive work over evaluated states.
A binary prefix code has no whole codeword as another's initial segment, permitting immediate sequential decoding. Uniquely decodable code lengths satisfy Σ2⁻ˡⁱ≤1; conversely positive integer lengths satisfying the inequality admit a prefix code. Expected length is at least source entropy.
In a connected undirected weighted graph, if a set of chosen edges lies within some minimum spanning tree and a cut crosses none of them, a lightest edge crossing that cut can be added while preserving this invariant. Equal-weight choices need not occur in every optimum.
For a 3CNF formula with m clauses, make a vertex for each literal occurrence. Join occurrences from different clauses unless their literals are complementary. The formula is satisfiable exactly when the graph has a clique of size m: choose one true occurrence per clause; conversely the clique's consistent literals extend to an assignment.
A directed network flow respects nonnegative capacities and conserves flow at vertices other than source s and sink t. Residual capacities allow unused forward flow and undoing existing flow. A feasible flow is maximum exactly when no residual s–t path exists, equivalently when its value equals the capacity of some s–t cut.
A finite directed graph admits an order placing u before v for every edge u→v exactly when it is acyclic. Full DFS's reverse finishing order is topological for a DAG. Checking every edge against that order detects a cycle otherwise; with adjacency lists the whole procedure takes O(|V|+|E|).
A logspace many-one reduction computes f with x∈A exactly when f(x)∈B, using a read-only input, O(log n) work tape and write-only output. Directed s–t reachability is NL-complete under these reductions: bounded path guessing uses logarithmic space, and each NL computation reduces to its polynomial-size configuration graph.