Why this matters when you build with AI
Many everyday problems pair one kind of thing with another kind: workers with jobs, students with rooms, drivers with routes. A bipartite graph is a graph with two sides, where every edge goes from one side to the other. A matching is a set of edges where no vertex appears twice. Assigning as many workers as possible to jobs is a maximum matching problem.
AI tools often answer these with a greedy rule: go through the workers in order and give each one the first free job. Greedy is fast, and it is often wrong by a lot. Take three workers and three jobs, where worker 0 can do jobs 0 or 1, worker 1 can only do job 0, and worker 2 can do jobs 1 or 2. Greedy gives worker 0 job 0, then worker 1 finds job 0 taken, and worker 2 takes job 1. Two assignments. The right answer is three: worker 0 takes job 1, worker 1 takes job 0, and worker 2 takes job 2. Greedy cannot undo its first choice, and the flow method in this lesson can.
The min-cut part is harder to spot in a problem. A common first answer treats "choose a set of tasks with prerequisites to maximise profit" as a sorting or dynamic programming problem, which can go wrong once the prerequisites form a graph with many links. A min cut solves it exactly, and the cut itself tells you which tasks to choose. The modelling step is the part to check, and the way to check it is a brute-force search over all choices on small inputs.
A prompt that asks for the model and the recovery step, not only the number:
Given workers, jobs and allowed pairs (up to 300 on each side), find the largest set of
assignments where each worker and each job is used at most once. Use a max flow or
Hopcroft-Karp. Then also return a minimum vertex cover of the allowed-pairs graph and
show that its size equals the matching size. Say what you tested by brute force and on what sizes.A good answer uses one of the two methods, builds the cover from the alternating search, and states the sizes it compared. A weak answer prints only the matching size, or states "by König's theorem" without giving the construction.
Terms used
- A bipartite graph has two sides, here called left and right. Every edge joins a left vertex to a right vertex.
- A matching is a set of edges with no shared endpoint. A maximum matching has the most edges possible.
- A free vertex is one that no matching edge touches.
- An augmenting path starts at a free left vertex, goes along an edge that is not matched, then along a matched edge back, and so on, until it reaches a free right vertex. Flipping the edges along it makes the matching one edge larger.
- A vertex cover is a set of vertices such that every edge has at least one endpoint in the set.
- A min cut is a split of a flow network into a source side and a sink side with the smallest total capacity of edges going from the source side to the sink side.
- Project selection is a closure problem: choose some items, each with a profit that may be negative, such that if an item is chosen, the items it depends on are chosen too.
- An infinite edge is an edge with a capacity larger than any finite cut, so a min cut never cuts it. It forces a rule: if the tail is on the source side, the head must be too.
Matching as max flow
Turn the bipartite graph into a flow network with three kinds of edges:
- from the source to each left vertex, capacity 1,
- from each left vertex to each right vertex it can match, capacity 1,
- from each right vertex to the sink, capacity 1.
Every unit of flow goes source, left vertex, right vertex, sink. Each left vertex takes at most one unit in, and each right vertex sends at most one unit out. So each unit of flow is one matched pair. Every capacity is 1, so a flow splits into unit paths, and each unit path is one matched pair. So the max flow equals the maximum matching.
The residual graph gives the augmenting paths. A path from the source to the sink in the residual graph goes through a forward edge that is unused, then may go backward along a used edge (undoing a pair), and so on. That is the same as the augmenting path of the matching. Dinic's algorithm from the previous lesson finds them in phases, so this method is fast on unit capacities.
Worked example with the three workers and three jobs above. The allowed pairs are (0,0), (0,1), (1,0), (2,1) and (2,2), written as worker and job, with 0-based numbers. The program in this lesson prints four numbers: the Hopcroft-Karp matching size, the flow value, the cover size and a check flag. Its output is:
3 3 3 1The matching is 3, the flow is 3, the cover has 3 vertices, and the flag 1 means the cover touches every edge and has the same size as the matching.
The augmenting path in this example, step by step. A greedy first pass gives worker 0 job 0 and worker 2 job 1. Worker 1 can only take job 0, which is taken by worker 0. Search from worker 1: it reaches job 0, which is matched to worker 0. Worker 0 can move to job 1, which is matched to worker 2. Worker 2 moves to job 2, which is free. Flipping the path gives worker 1 job 0, worker 0 job 1 and worker 2 job 2. Three pairs.
Hopcroft-Karp: many augmenting paths per phase
Hopcroft and Karp published an algorithm for maximum bipartite matching in SIAM Journal on Computing in 1973, volume 2, issue 4, pages 225 to 231. It finds augmenting paths in phases, like Dinic. Each phase does two things:
- A BFS starts from all free left vertices and alternates: left to right along an unmatched edge, then right to left along a matched edge. It records the distance of each left vertex. It stops the search at the first layer where a free right vertex appears.
- A DFS finds vertex-disjoint augmenting paths that follow the layers, one per free left vertex, and flips them.
The number of phases is at most about the square root of the number of vertices, and each phase is linear in the edges. So the total is O(E * sqrt(V)), the bound that the JGraphT documentation states for its implementation of the same algorithm. Hopcroft-Karp and the flow method give the same answer, and the program checks that on every test.
The code below is the matching class I compiled and tested. It has a current-arc pointer it[u], the same idea as in the previous lesson. A left vertex that fails in a phase is marked with distance -1 for the rest of that phase.
#pragma once
#include <algorithm>
#include <queue>
#include <vector>
// Hopcroft-Karp maximum bipartite matching.
// Left vertices 0..L-1, right vertices 0..R-1, edges added with add_edge(u, v).
struct HopcroftKarp {
int L, R;
std::vector<std::vector<int>> adj;
std::vector<int> matchL, matchR, dist, it;
HopcroftKarp(int L, int R) : L(L), R(R), adj(L), matchL(L, -1), matchR(R, -1), dist(L), it(L) {}
void add_edge(int u, int v) { adj[u].push_back(v); }
// BFS from every free left vertex. dist[u] = number of matched edges on the
// shortest alternating path from a free left vertex to u. Returns true if a
// free right vertex is reachable.
bool bfs() {
std::queue<int> q;
bool found = false;
for (int u = 0; u < L; ++u) {
if (matchL[u] < 0) {
dist[u] = 0;
q.push(u);
} else {
dist[u] = -1;
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
int w = matchR[v];
if (w < 0) {
found = true;
} else if (dist[w] < 0) {
dist[w] = dist[u] + 1;
q.push(w);
}
}
}
return found;
}
// Tries to find one augmenting path from u that follows dist+1 steps.
bool dfs(int u) {
for (int& i = it[u]; i < static_cast<int>(adj[u].size()); ++i) {
int v = adj[u][i];
int w = matchR[v];
if (w < 0 || (dist[w] == dist[u] + 1 && dfs(w))) {
matchL[u] = v;
matchR[v] = u;
return true;
}
}
dist[u] = -1; // dead end for the rest of this phase
return false;
}
int run() {
int result = 0;
while (bfs()) {
std::fill(it.begin(), it.end(), 0);
for (int u = 0; u < L; ++u)
if (matchL[u] < 0 && dfs(u)) ++result;
}
return result;
}
};König's theorem: the cover that proves the matching
König's theorem says that in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover. Dénes König published this result in Hungarian in 1931, in the journal Matematikai és Fizikai Lapok, under the title "Gráfok és mátrixok" (Graphs and matrices).
The theorem is useful because the cover is a certificate. If you find a matching of size 3 and a cover of size 3, no larger matching is possible, because every matched edge needs its own cover vertex. The cover is the proof.
The construction uses the matching you already have:
- Start an alternating search from every free left vertex.
- From a left vertex, follow every edge to a right vertex and mark the right vertex.
- From a marked right vertex, follow its matched edge back to its left vertex and mark that left vertex.
- The cover is all left vertices that were not marked, plus all right vertices that were marked.
Worked example by hand: edges (0,0), (0,1), (1,0) and (2,1), with the matching 0-0 and 2-1. Left vertex 1 is free. Search from it: it reaches right vertex 0, which is matched to left vertex 0, so left 0 is marked. Left 0 reaches right 1, which is matched to left 2, so left 2 is marked. Marked left: 0, 1, 2. Marked right: 0 and 1. No left vertex is unmarked, so the cover is the marked right vertices 0 and 1. Size 2, which equals the matching size. Every edge touches right 0 or right 1, so the cover is valid.
The code in the next section builds this cover and checks that it covers every edge. It was tested on 2000 random graphs with up to 6 vertices per side, against a brute-force matching.
Min cut extraction
After a max flow, the source side of a min cut is the set of vertices you can reach from the source in the residual graph. The class Dinic from the previous lesson has source_side. The cut edges are the edges from that set to its complement. Their total capacity equals the max flow.
Two uses of this in the rest of the lesson:
- In project selection, the source side is the chosen set.
- In grid labelling, the source side is the set of cells labelled 1.
Both only work if the construction gives the right meaning to each cut edge, as the next two sections show.
Project selection as a min cut
Problem. There are n projects. Project i has a profit p[i], which may be negative. Some pairs say that project i needs project j, meaning that choosing i forces choosing j. Find the set of projects that gives the largest total profit, and that respects all the needs.
Construction. Add a source s and a sink t.
- For a project with
p[i] > 0, add an edge fromstoiwith capacityp[i]. Cutting it means the project is on the sink side, so it is not chosen, and we losep[i]. - For a project with
p[i] < 0, add an edge fromitotwith capacity-p[i]. Cutting it means the project is on the source side, so it is chosen, and we pay-p[i]. - For "i needs j", add an edge from
itojwith an infinite capacity. Ifiis on the source side andjis on the sink side, that edge would be cut, which costs infinity. So the cut never allows it.
Then the best profit is the sum of the positive profits minus the min cut. The chosen set is the source side, minus s itself.
Why the arithmetic works: each project pays either its positive profit (lost if it is not chosen) or its negative cost (paid if it is chosen). The min cut is the smallest total of lost profit and paid cost over all closed choices, so subtracting it from the sum of positive profits gives the largest profit.
Worked example: projects 0 to 4 with profits 6, -4, 5, -1, 2, and the needs 0 needs 1, 0 needs 3, 2 needs 3, and 4 needs 2. The program prints the best profit, then the chosen projects:
8
0 1 2 3 4Check by hand. Choosing everything gives 6 - 4 + 5 - 1 + 2 = 8. Every need is met, because all projects are chosen. Is there a better set? Dropping project 0 gives -4 + 5 - 1 + 2 = 2, which is worse. Dropping project 4 gives 6, also worse. The program's answer agrees with the hand check, and the random tests below compare it with trying all 2^n subsets.
The point to notice: the chosen set is recovered from the cut. You do not need a second search. The source side after the flow contains exactly the chosen projects, and the sink side contains the rest.
Grid labelling as a min cut
Problem type. Each cell of a grid gets label 0 or 1. Labelling cell i with 0 costs c0[i], and with 1 costs c1[i]. For each pair of neighbouring cells (up and down, or left and right) that get different labels, add a penalty P. Find the labelling with the smallest total cost. This is the kind of problem that appears in image cleanup (keep the background smooth), in choosing seats in a grid, or in deciding which cells of a map a tool should mark.
Construction. For each cell i, add an edge from s to i with capacity c0[i]. Its cut means cell i is on the sink side, so it has label 0 and we pay c0[i]. Add an edge from i to t with capacity c1[i]. Its cut means cell i is on the source side, label 1, and we pay c1[i]. For each neighbouring pair i and j, add an edge i -> j with capacity P and an edge j -> i with capacity P. If the two cells have different labels, exactly one of those two edges goes from the source side to the sink side, so the penalty P is paid exactly once. If the labels agree, neither edge is cut.
The label of each cell is read from the source side: label 1 if reachable from s in the residual graph, label 0 otherwise.
Worked example: a 2 by 2 grid with penalty P = 1. Cell costs (c0, c1) in row-major order are (0,3), (3,0), (1,4) and (2,2). The program prints the min cost and the labels:
5
0100Check by hand. Labels 0, 1, 0, 0. Costs: cell 0 with label 0 costs 0, cell 1 with label 1 costs 0, cell 2 with label 0 costs 1, cell 3 with label 0 costs 2. Sum 3. Neighbour pairs with different labels: cells 0 and 1 (labels 0 and 1), and cells 1 and 3 (labels 1 and 0). Two penalties of 1 each. Total 5, which matches.
A limit to know: this construction handles two labels with a penalty that is the same for both directions and never negative. Three labels, or penalties that depend on which label is on which side, need a different construction, and you should not copy this one there without a new check.
The C++17 program
The program below is the one tested on random inputs. It has three modes, chosen by the first word of the input: match, project and grid. It uses Dinic from the previous lesson, saved in dinic.hpp, and the HopcroftKarp class above, saved in hk.hpp.
// Modes (first word of stdin):
// match L R M, then M lines "u v" -> prints "hk flow cover ok"
// project n, n profits, m, then m lines "i j" (i needs j) -> prints "best" and chosen ids
// grid H W P, then H*W lines "c0 c1" (cost if cell is 0 / 1), P per differing neighbour pair
// -> prints "cost" and the labels as a string of 0 and 1
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include "dinic.hpp"
#include "hk.hpp"
static const long long INF = 1000000000000LL;
int main() {
char mode[32];
if (scanf("%31s", mode) != 1) return 0;
if (!strcmp(mode, "match")) {
int L, R, M;
scanf("%d %d %d", &L, &R, &M);
std::vector<std::pair<int, int>> E(M);
for (auto& p : E) scanf("%d %d", &p.first, &p.second);
// 1. Hopcroft-Karp
HopcroftKarp hk(L, R);
for (auto [u, v] : E) hk.add_edge(u, v);
int hkSize = hk.run();
// 2. Matching as max flow: s -> left (1), left -> right (1), right -> t (1)
int s = 0, t = L + R + 1;
Dinic d(L + R + 2);
for (int u = 0; u < L; ++u) d.add_edge(s, 1 + u, 1);
for (int v = 0; v < R; ++v) d.add_edge(1 + L + v, t, 1);
std::vector<int> ids;
for (auto [u, v] : E) ids.push_back(d.add_edge(1 + u, 1 + L + v, 1));
long long flow = d.max_flow(s, t);
// 3. Koenig: alternating BFS from free left vertices on the HK matching.
std::vector<bool> visL(L, false), visR(R, false);
std::vector<std::vector<int>> adj(L);
for (auto [u, v] : E) adj[u].push_back(v);
std::vector<int> q;
for (int u = 0; u < L; ++u)
if (hk.matchL[u] < 0) {
visL[u] = true;
q.push_back(u);
}
for (size_t h = 0; h < q.size(); ++h) {
int u = q[h];
for (int v : adj[u]) {
if (visR[v]) continue;
visR[v] = true;
int w = hk.matchR[v]; // always matched, or the matching was not maximum
if (w >= 0 && !visL[w]) {
visL[w] = true;
q.push_back(w);
}
}
}
// cover = (left not visited) + (right visited)
std::vector<std::pair<int, int>> cover; // (side, id)
int coverSize = 0;
for (int u = 0; u < L; ++u)
if (!visL[u]) ++coverSize;
for (int v = 0; v < R; ++v)
if (visR[v]) ++coverSize;
bool coverOk = true;
for (auto [u, v] : E)
if (visL[u] && !visR[v]) coverOk = false; // edge missed by the cover
bool ok = (hkSize == flow) && (coverSize == hkSize) && coverOk;
printf("%d %lld %d %d\n", hkSize, flow, coverSize, ok ? 1 : 0);
return 0;
}
if (!strcmp(mode, "project")) {
int n;
scanf("%d", &n);
std::vector<long long> p(n);
for (auto& x : p) scanf("%lld", &x);
int m;
scanf("%d", &m);
int s = n, t = n + 1;
Dinic d(n + 2);
long long positive = 0;
for (int i = 0; i < n; ++i) {
if (p[i] > 0) {
d.add_edge(s, i, p[i]);
positive += p[i];
} else if (p[i] < 0) {
d.add_edge(i, t, -p[i]);
}
}
for (int k = 0; k < m; ++k) {
int i, j;
scanf("%d %d", &i, &j);
d.add_edge(i, j, INF); // taking i forces taking j
}
long long cut = d.max_flow(s, t);
printf("%lld\n", positive - cut);
auto side = d.source_side(s);
bool first = true;
for (int i = 0; i < n; ++i)
if (side[i]) {
printf(first ? "%d" : " %d", i);
first = false;
}
printf("\n");
return 0;
}
if (!strcmp(mode, "grid")) {
int H, W, P;
scanf("%d %d %d", &H, &W, &P);
int N = H * W;
int s = N, t = N + 1;
Dinic d(N + 2);
for (int i = 0; i < N; ++i) {
long long c0, c1;
scanf("%lld %lld", &c0, &c1);
d.add_edge(s, i, c0); // cut when cell i is on the sink side (label 0)
d.add_edge(i, t, c1); // cut when cell i is on the source side (label 1)
}
for (int r = 0; r < H; ++r)
for (int c = 0; c < W; ++c) {
int i = r * W + c;
if (c + 1 < W) {
d.add_edge(i, i + 1, P);
d.add_edge(i + 1, i, P);
}
if (r + 1 < H) {
d.add_edge(i, i + W, P);
d.add_edge(i + W, i, P);
}
}
long long cost = d.max_flow(s, t);
auto side = d.source_side(s);
printf("%lld\n", cost);
std::string labels;
for (int i = 0; i < N; ++i) labels += side[i] ? '1' : '0';
printf("%s\n", labels.c_str());
return 0;
}
return 0;
}The inputs for each mode, as the program reads them, are these lines:
match 3 3 5
0 0
0 1
1 0
2 1
2 2
project 5
6 -4 5 -1 2
4
0 1
0 3
2 3
4 2
grid 2 2 1
0 3
3 0
1 4
2 2Each block is a separate run: the first is the matching example, the second the project example, and the third the grid example. The program reads whitespace, so line breaks between the numbers do not matter.
Testing against brute force
The matching check compares three numbers: the Hopcroft-Karp size, the flow size and the cover size, against a brute-force search that tries every subset of left vertices. The project check compares the best profit with a search over all 2^n subsets that respect the needs, and it also checks that the chosen set returned by the program respects the needs and has that profit. The grid check compares the cost with a search over all 2^(H*W) labellings, and it recomputes the cost of the labels the program printed.
I ran 2000 random seeds, and each seed went through all three modes: matching with up to 6 vertices per side, projects with up to 8 projects, and grids of up to 3 by 3 cells. Result: 0 failures in each mode. A rerun after the final header change gave 0 failures on 1000 seeds. This is evidence on small inputs, not a proof, and the brute force only reaches small sizes.
Brute-force matching in plain Python, a self-contained program with no input, so it can run as written:
Its output on this machine is:
brute matching size 3This agrees with the C++ output 3 3 3 1 in the matching section.
Complexity
- Matching by flow: Dinic on a unit-capacity network. The bound from the previous lesson applies,
O(E * min(sqrt(E), V^(2/3))), withVvertices andEedges. - Hopcroft-Karp:
O(E * sqrt(V)). - König cover: one search over the graph,
O(V + E). - Project selection: one max flow on
n + 2vertices andn + medges. The general Dinic bound isO(V^2 E). Real inputs may be much faster. - Grid labelling: one max flow on
H * W + 2vertices and about4 * H * Wedges plus the source and sink edges. The same Dinic bound applies. I did not time large grids.
Scope: the matching bounds are the standard ones for these algorithms, and the Hopcroft-Karp bound is stated in the JGraphT documentation for its implementation. The König theorem and the min-cut equality are classical results. The timing numbers in the previous lesson were measured on one machine and are only a sanity check.
Common mistakes
Greedy matching in input order. Symptom: on the three-worker example, the answer is 2 where the answer is 3. Use flow or Hopcroft-Karp. A greedy answer is a lower bound, not the maximum.
Missing edge direction in the matching flow. Symptom: the flow is 0 or too small. The edges must go source to left, left to right, right to sink. If you add the right-to-sink edges as sink-to-right, nothing reaches the sink.
Forgetting INF on the needs edges. Symptom: a project set that breaks a need is reported as the best. The need edge must have an infinite capacity, so that a cut can never separate i from j in that direction.
Reading the chosen set from the sink side. Symptom: the program prints the projects you did not want. The chosen set is the source side. Check it on the worked example: the output should be 0 1 2 3 4.
Forgetting that the grid penalty is paid once. Symptom: differing neighbours cost twice. Each neighbour pair gets two edges, one in each direction, and exactly one of them is cut when the labels differ. Do not add a third edge.
Using a min cut with a negative penalty. Symptom: an edge gets a negative capacity, and the flow code returns a value that the brute force does not agree with. The construction here needs non-negative penalties for differing labels. Check the sign before you apply it.
Trusting one passing sample. Symptom: the sample output is right, and a random test with a different seed fails. Always compare with a brute force on random small inputs, with several seeds.
Hands-on exercise on your machine
Create a folder, put dinic.hpp, hk.hpp and the program above into it, and compile:
g++ -std=c++17 -O2 -Wall -Wextra -o tools tools.cppSave the three inputs from the section "The inputs for each mode" in files named match.txt, project.txt and grid.txt, and run ./tools < match.txt, and so on. Check the outputs against the ones in this lesson: 3 3 3 1, then 8 and 0 1 2 3 4, then 5 and 0100.
Then write one new problem of your own. Choose a small rule with three parts: a set of pairs, a set of profits with prerequisites, or a grid with costs. Write the brute force first, in Python, for inputs of up to 8 items. Then write the flow model and compare on 500 random inputs.
Prompt to use with an AI tool, once you have a model:
I modelled my problem as a min cut. Here is the construction and the code.
Write a brute-force checker in Python for inputs up to 8 items, and a loop that compares
the brute force with the C++ program on 500 random inputs. Print the first 3 disagreements
with the seed. Then list two inputs that you think are hard for my construction
(for example, all profits negative, or a cycle of needs) and say what the program
should print for each, by hand.A good answer keeps the brute force simple, prints the seed of each disagreement, and gives hand answers for the hard inputs. A weak answer checks only the sample, or changes the construction to match the brute force.
Checklist
- The matching flow has source to left, left to right, right to sink, all with capacity 1.
- The matching size from Hopcroft-Karp equals the flow value.
- The cover from the alternating search has the same size as the matching, and it touches every edge.
- In a project problem, positive profits go from the source, negative costs go to the sink, and every need is an infinite edge from the dependent project to the required one.
- The chosen set is read from the source side, and it respects every need.
- In a grid, each neighbouring pair gets two edges of capacity
P, and the penalty is non-negative. - Each result is compared against a brute force on random small inputs.
Summary
A bipartite matching is a flow of unit capacities, and Hopcroft-Karp is a faster way to get the same number. The alternating search that finds the matching also gives a minimum vertex cover, which proves that the matching is largest. Project selection and grid labelling are min cuts: the cut edges pay the costs, and the source side is the answer. The modelling step is what to check, and a brute force on small cases is how to check it.
Practice
Practice 1. Students and rooms. Four students, 0 to 3, and four rooms, 0 to 3. Student 0 can use rooms 0 and 1. Student 1 can use room 0. Student 2 can use rooms 1 and 2. Student 3 can use room 2 only. Find the largest number of students that can each get a different room, and give a matching.
Hint: count the rooms that any student wants. Then compare with the number of students.
Show the answer
The maximum is 3. Only rooms 0, 1 and 2 appear in the lists, so at most three students can get a room. One matching of size 3: student 1 gets room 0, student 0 gets room 1, and student 3 gets room 2. Student 2 is left out. The program prints 3 3 3 1 for the input match 4 4 6 with the edges 0 0, 0 1, 1 0, 2 1, 2 2, 3 2, which agrees with this count.
Practice 2. Project chain. Projects 0 to 3 with profits 4, -3, 2, -2. Project 0 needs project 1. Project 2 needs project 3. Project 1 needs project 3. Find the best profit and the chosen projects, first by hand, then with the program.
Hint: try each closed set. A set is closed if every need of a chosen project is also chosen. Start from the set of all projects and remove those that cost more than they give.
Show the answer
The set of all projects has profit 4 - 3 + 2 - 2 = 1. Closed sets: {0, 1, 2, 3} gives 1. {2, 3} gives 0. {1, 3} gives -5. {3} gives -2. {} gives 0. {0, 1, 3} gives -1. The best is 1 with all four projects. The program prints 1 and then 0 1 2 3, as I checked on the scratch input. If it prints something else, check the needs edges: each need must go from the dependent project to the required one, with an infinite capacity.
Practice 3. A 1 by 3 grid with penalty P = 2. Cells 0, 1 and 2 in a row. Costs (c0, c1) are (0, 5), (4, 0) and (0, 5). Find the best labelling by hand, then the cost.
Hint: compare the cost of making all three cells 0 with the cost of labelling the middle cell 1 and the others 0. Each neighbour pair with different labels adds 2.
Show the answer
All zeros: costs 0 + 4 + 0 = 4, no differing pairs, total 4. Middle cell 1, others 0: costs 0 + 0 + 0 = 0, two differing pairs at 2 each, total 4. All ones: costs 5 + 0 + 5 = 10. Middle cell 1, outer cells 1: costs 5 + 0 + 5 = 10. The best value is 4, and two labellings reach it. The program prints 4 and then 000, which is one of the two optimal labellings. On other inputs it may print a different optimal labelling, so recompute the cost of whatever it prints.
Practice 4. For the three-worker matching example in this lesson, find a minimum vertex cover by the König construction, when the matching is 1 with job 0, 0 with job 1 and 2 with job 2 (a perfect matching). Explain why the construction gives all the workers.
Hint: if no left vertex is free, the search starts from nothing.
Show the answer
The matching is perfect, so no left vertex is free. The alternating search starts from an empty set and marks nothing. The cover is all unmarked left vertices, which are all three workers. The cover {worker 0, worker 1, worker 2} has size 3, equals the matching size, and touches every edge.
Practice 5. Explain in two sentences why the chosen set in a project problem is the source side of the min cut, and not the sink side.
Hint: think about which edge is cut for a positive profit project that is not chosen.
Show the answer
A project with positive profit that is not chosen sits on the sink side, so its source edge is cut and that profit is lost. A project with negative cost that is chosen sits on the source side, so its edge to the sink is cut and that cost is paid, which is exactly the rule for the chosen set.