final Flashcards
spanning tree
A subset of edges of a graph that connects all the vertices without forming a cycle
MST
a spanning tree with the smallest possible total edge weight
Generic-MST Algorithm
An algorithm for finding a minimum spanning tree by adding safe edges iteratively
safe edge
An edge that can be added to the current tree without violating its properties as part of an MST
cut
a partition of the vertices of a graph into two disjoint subsets
light edge
the smallest weight edge crossing a given cut
edge replacement
The process of adding and removing edges to maintain a spanning tree structure
Prim’s Algorithm
A greedy algorithm that grows an MST starting from an arbitrary vertex
Kruskal’s Algorithm
A greedy algorithm that builds an MST by sorting edges and adding them while avoiding cycles
Union-Find Data Structure
A data structure that efficiently supports union and find operations for disjoint sets
Single-Source Shortest Path (SSSP)
The problem of finding the shortest paths from a single source vertex to all other vertices
relaxation
The process of updating an estimate of the shortest path in shortest-path algorithms
Dijkstra’s Algorithm
An algorithm for solving the SSSP problem on graphs with non-negative weights
Fibonacci Heaps
A data structure used to improve the running time of algorithms like Prim’s and Dijkstra’s
Flow Network
A directed graph with a capacity assigned to each edge, used to model flow problems
(s, t)-Flow
A function that represents the flow of material from source s to sink t under capacity and conservation constraints
Feasible Flow
A flow that satisfies capacity constraints
residual graph
A graph showing remaining capacities and possible reverse flows after some flow has been pushed
Max-Flow Min-Cut Theorem
States that the maximum value of an (s, t)-flow equals the capacity of the minimum (s, t)-cut
Augmenting Path
A path in the residual graph where additional flow can be pushed from s to t
Ford-Fulkerson Algorithm
A method to compute the maximum flow in a flow network by iteratively augmenting flow
along paths in the residual graph
Edmonds-Karp Algorithm #1
An implementation of Ford-Fulkerson that selects the widest augmenting path (the one with the largest bottleneck value)
Edmonds-Karp Algorithm #2
An implementation of Ford-Fulkerson that selects the shortest augmenting path in terms of edges (the smallest number of edges)
Bipartite Graph
A graph whose vertex set can be divided into two disjoint sets such that every edge connects a vertex from one set to the other
Matching
A subset of edges in a graph such that no two edges share a vertex
Maximum Matching
A matching that contains the largest possible number of edges
Tractability
A problem is
considered tractable if it can be solved in polynomial time, making it reasonably solvable
Hamiltonian Cycle
A simple cycle in a graph that visits every vertex exactly once
Hamiltonian Cycle Problem
The decision problem of determining whether a graph contains a Hamiltonian cycle
Decision Problem
A problem with a yes/no answer, such as ”Does the graph have a flow of value k?”
Search/Optimization Problem
A problem where the goal is to find the best solution, such as ”What is the maximum flow value?”
Reduction
The process of transforming one problem into another in polynomial time to compare their hardness.
NP
Nondeterministic Polynomial-Time
The class of problems that can be guessed and verified in polynomial time
NP-Complete
A problem that is in NP and is as hard as every other problem in NP
Boolean Satisfiability Problem (SAT)
The decision problem of determining whether there exists an assignment of Boolean values to variables that satisfies a given CNF formula
P = NP
A major unsolved question in computer science, asking whether every problem in NP can be solved in polynomial time
Traveling Salesman Problem (TSP)
The problem of finding the shortest possible route that visits each city exactly once and returns to the starting city
Approximation Algorithm
An algorithm that provides a solution within a provable factor α of the optimal solution
ALG / OPT < α
Randomized Algorithm
An algorithm that uses randomness and may provide correct solutions with high probability or run in polynomial time with high probability.
respects (cut)
A cut (S, S ̄) respects A ⊆ E if no edge in A crosses (S, S ̄)
sparse graph
O(n)
dense graph
O(n^2)
