Tensions in Practice: Few crossing links in tension with balanced parts¶
Graph partition · six equal work units
Six equally sized work units are connected by seven undirected links: AB, BC, BD, CD, CE, DE and EF. A cut assigns every unit to one of two nonempty parts; its cost here is the number of links crossing between them. Isolating A crosses only AB but leaves a 1-to-5 split. Putting A, B and C together makes the parts equal while crossing three links. Neither objective is a substitute for the other.
Minimize links crossing the boundary
Separate a part while interrupting or coordinating as few links as possible.
Balance the work in the two parts
Give both parts the same number of stipulated equal work units.
Why these aims pull against each other
The raw minimum can isolate a peripheral unit. Requiring equal part sizes excludes that cheapest cut and changes which boundary is admissible.
Choose an arrangement to see what changes and what remains difficult.
Finite illustrative comparisons. Text states carry the meaning; color is not a measured score or universal preference.
What this choice protects
What it costs
When it fits
Compare the arrangements
Fewest links
Put A on the left and every other unit on the right.
| Part | |
|---|---|
| A | Left |
| B | Right |
| C | Right |
| D | Right |
| E | Right |
| F | Right |
| Crossing | AB |
| Sizes | 1 / 5 |
- What it protects
- Only AB crosses. This is a minimum nonempty cut: the connected graph has no zero-link cut and this one uses one link.
- What it costs
- Five work units remain together; the partition does not distribute work equally.
- When it fits
- Cheap separation itself is the goal, such as identifying a weakly attached part, and equal work is not required.
Illustration note: Every edge has unit crossing cost and every node has unit work. A minimum cut is useful under this stated objective, not presented as a failed balance algorithm.
Equal parts
Put A, B and C on the left, and D, E and F on the right.
| Part | |
|---|---|
| A | Left |
| B | Left |
| C | Left |
| D | Right |
| E | Right |
| F | Right |
| Crossing | BD, CD, CE |
| Sizes | 3 / 3 |
- What it protects
- Both parts contain three work units under the declared equal-work assumption.
- What it costs
- BD, CD and CE cross, so this displayed balanced cut carries three times as many crossing links as the one-link cut.
- When it fits
- Comparable work per part is required and these additional crossing costs are acceptable.
Illustration note: This table exhibits a balanced cut, not a claim about a general partition solver or universal optimality. The underlying edges and weights are unchanged.
What this illustration does—and does not—establish
Cut: Balanced Partition versus Degenerate Cut (scalar/local-global) supplies the balance constraint; Cut: Cut as Bottleneck versus Cut as Cleavage (frame duality) keeps the purpose of a cut explicit. The finite graph makes crossing sets independently countable.
- Equal node counts mean equal work only because that equivalence is explicitly stipulated here.
- The graph is undirected and connected; these are partition links, not a flow solution.
- Changing edge weights, work sizes or required part counts changes the problem.
Source entries
Cut
Cut: Balanced Partition versus Degenerate Cut (scalar/local-global) supplies the conflict examined here.
Balanced Partition versus Degenerate Cut (scalar/local-global)
Searching for the smallest cut without a balance constraint invites trivial answers — the cheapest cut often just shaves off a single peripheral vertex, which is why normalized and conductance cuts divide by part size.
Cut as Bottleneck versus Cut as Cleavage (frame duality)
Small cuts carry two dual readings — a flow bottleneck to be widened, or a module seam to be respected — and the same edge-set demands opposite interventions under each.