1
Read a graph from one walk
Discovery and finish times, the four edge classes, bridges and cut vertices, topological order and strongly connected components — each one arithmetic on the same two numbers, and each with the count it cost.
Course · Algorithms
Graph Algorithms
Discrete Mathematics defined graphs and ran two algorithms on them. This course builds eleven, proves each correct, and counts what each one does on the graph you type. It is also where an algorithm first certifies its own answer: everywhere else on this path a lesson puts a measured count beside a proved bound, and here the maximum flow comes back with a cut of equal capacity attached.
d[v], f[v] two times per vertex; the intervals nest or are disjoint
low[v] > d[u] the tree edge above v is a bridge
cut property the lightest edge leaving S is in some minimum spanning tree
relax(u, v) d[v] = min(d[v], d[u] + w) the whole of shortest paths
max flow = min cut the failed search IS the certificate
What this course is about
- Subject
- Algorithms
- Lessons
- 13
- Format
- Interactive
Overview
What you will be able to do
By the end you can read four different facts off one traversal, justify every edge a minimum-tree algorithm takes by naming a cut, choose a shortest-path method from what the weights and the cycles allow, and produce the certificate that proves a flow maximum.
2
Justify an edge by naming a cut
State and prove the cut and cycle properties, then show that both minimum-tree algorithms are the same lemma with a different rule for choosing the cut — and say whether the tree you found is the only one.
3
Choose a shortest-path method from the input
Nearest-first where no weight is negative, rounds where they are, one pass where there are no cycles at all; and in each case say what the method assumes rather than what it costs.
4
Produce a certificate, not just an answer
Run the augmenting-path method, read the minimum cut off the search that failed, check its capacity against the flow's value, and translate both back into a matching and a vertex cover.
Lessons
13 lessons
One traversal first, because four of the thirteen results are it read differently; then weights, and the lemma that justifies a greedy choice; then shortest paths, as one step under three schedules and two special cases; then flow, where the certificate arrives with the answer.
Depth-First Search and the TimestampsRun one walk, write two numbers on every vertex, and classify every arc from those numbers alone.Not marked
Topological OrderProduce an order in which every task follows its prerequisites, two different ways, and count how many such orders exist.Not marked
Bridges and Cut VerticesAdd one number per vertex to the same walk and find every edge and vertex whose removal breaks the graph apart.Not marked
Strongly Connected ComponentsPartition a digraph into the groups whose members can all reach each other, in two walks, and collapse it to something acyclic.Not marked
The Cut PropertyProve the one lemma both minimum-tree algorithms rest on, against an enumeration of every spanning tree the graph has.Not marked
Kruskal's AlgorithmSort the edges, take each one unless its ends are already joined, and count the union-find work that decides.Not marked
Prim's AlgorithmGrow one tree across its own boundary, step the heap, and watch a stale entry come out of it.Not marked
Relaxation and Dijkstra's ScheduleApply one line of arithmetic in three different orders, reach the same distances, and count what each order costs.Not marked
Negative Weights and Bellman–FordSweep every arc once per round, watch each label become final, and get a negative cycle back as the cycle itself.Not marked
Shortest and Longest Paths in a DAGRelax each arc exactly once in topological order, then flip the sign and read the critical path off the same pass.Not marked
Augmenting PathsPush flow along a path, discover that a first choice has to be undone, and watch a backward arc undo it.Not marked
Max Flow and Min CutRead the certificate off the failed search, and check it against every cut the network has.Not marked
Bipartite MatchingTurn a pairing problem into a unit-capacity network, and read the matching, the cover and the obstruction off one run.Not marked
Recommended background
Discrete Mathematics in full, and by name: Graphs and Graph Models, Graph Representations, Paths and Connectivity, Bipartite Graphs, Breadth-First and Depth-First Search, Shortest Paths and Dijkstra's Algorithm, Trees, Spanning Trees and Minimum Spanning Trees, Big-O, Big-Omega and Big-Theta, Analysing Iterative Algorithms, Loop Invariants and Program Correctness, and Strong Induction; and from the data structures course on this path, Priority Queues and Binary Heaps and Union–Find, whose costs are quoted here and re-derived nowhere.
Practice suggestions
Move the starting vertex before you write a number down. The class of an arc, the work a heap does and the number of rounds a sweep needs all change with where the algorithm began; the distances, the tree weight and the flow value do not. Every lab on this course lets you move it, and the split between what moves and what does not is the course's main lesson about measurement.
Read a schedule as a separate thing from the step it schedules. “Relaxation and Dijkstra's Schedule”, “Negative Weights and Bellman–Ford” and “Shortest and Longest Paths in a DAG” perform identical arithmetic in three orders; what separates them is what each order assumes about the input.
Distrust a run that merely stopped. Three lessons here turn on the difference between “my search found nothing more” and “nothing more exists” — a maximal matching, a maximal flow, and a greedy pass that is neither. Only “Max Flow and Min Cut” closes that gap, and it closes it with an object you can check by hand.
What it does not cover
All-pairs shortest paths. The one-source methods here are enough for every claim the course makes, and filling a whole matrix is a dynamic program over which interior vertices are allowed — a shape this path develops later rather than here.
Modelling transformations on flow networks: splitting a vertex to cap what passes through it, unit capacities to count arc-disjoint routes, a super-source over several starts. They change the network and not the algorithm, and the catalogue is a separate skill from proving an algorithm correct.
Preflow-push, capacity scaling and the polynomial bounds on the number of augmentations. The augmenting-path method is developed and counted; how many augmentations it needs in the worst case is stated nowhere here.
Tarjan's one-pass strongly connected components, and Fibonacci heaps. Both are improvements on algorithms this course builds, neither changes a correctness argument, and the second changes a bound no lesson here depends on.