Enumerate graph bipartitions
Represent each nonempty split once and inspect which connections cross it.
Course lessons · 3 of 5
Count unique bipartitions, calculate a raw cut weight, and distinguish it from the laboratory’s normalized-cut score.
Useful background: Measure shared information
A bipartition has two nonempty sides
Choose a nonempty subset S of a node set V, leaving its nonempty complement on the other side. If the objective treats the two sides symmetrically, S and its complement represent the same split. Counting both wastes work and can distort reported totals.
For n labeled nodes, fix one anchor node on the first side. Each of the other n − 1 nodes chooses a side. Exclude the assignment that places every node with the anchor, leaving 2^(n − 1) − 1 unique nontrivial bipartitions.
Calculate the cut, then inspect its normalization
In a weighted undirected graph, the raw cut weight adds edges whose endpoints lie on different sides. Each crossing edge is counted once. The laboratory then computes normalized cut, NCut, by dividing that raw cut by each side’s volume and adding the two ratios.
A side’s volume is the sum of weighted node degrees on that side. An internal edge contributes twice to that volume, once through each endpoint; a crossing edge contributes once. Either side having zero volume makes this normalized objective undefined. A raw cut weight and an NCut score are different values, even for the same split.
The project’s normalized MIP benchmark uses conditional Gaussian entropies and an entropy normalizer, not this degree-volume formula. All three quantities must retain their definitions: raw edge cut, the laboratory’s NCut, and the manuscript’s normalized stochastic interaction.
Inspect the split {A,B} | {C,D}
1Define a four-node chain
Use edges A–B of weight one, B–C of weight two, and C–D of weight three. All unlisted edges have weight zero.
2Find crossing edges
A–B stays on the first side, and C–D stays on the second side. Only B–C crosses the split.
3Sum each crossing edge once
The raw cut weight is two. In this worked chain, the first side has volume four and the second has volume eight, so its normalized-cut score is 2/4 + 2/8 = 0.75. Four nodes have seven unique nontrivial bipartitions.
Make the idea respond
To reproduce a laboratory calculation, select 4 nodes, Chain, and bridge weight 2. This preset has edge weights 1, 2, 1, whereas the written example above uses 1, 2, 3. For the laboratory split {0,1} | {2,3}, the raw cut is 2, both side volumes are 4, and NCut = 2/4 + 2/4 = 1. Inspect the raw-cut and normalized-score columns separately.
Change one input at a time. Predict what should happen, then compare the computed result with your prediction.
Teaching model · computed in your browser
Find every graph partition
Change a tiny graph and examine every possible split. The minimum is computed by complete enumeration.
A and B are nonempty complementary node sets. cut(A, B) is the sum of edge weights crossing the split, counted once. vol(A) is the sum of weighted degrees of nodes in A, including both ends of internal edges; vol(B) is defined likewise. A zero volume makes this objective undefined. This is a normalized-cut teaching example, not the manuscript’s normalized minimum information partition (MIP). It does not calculate integrated information or benchmark Queyranne, annealing, or QAOA.
Try this: lower the bridge weight to zero. Inspect both the minimum and any undefined partitions. Then switch from two clusters to a cycle.
The default worked example is shown below.
For this split: cut(A, B) = 0.2; vol(A) = 6.2; vol(B) = 6.2. NCut = 0.2 / 6.2 + 0.2 / 6.2 = 0.0645. Every unordered, nonempty bipartition appears once because node A is fixed in the first part.
| Group A | Group B | Cut | vol(A) | vol(B) | NCut |
|---|---|---|---|---|---|
| A | B, C, D, E, F | 2 | 2 | 10.4 | 1.1923 |
| A, B | C, D, E, F | 2 | 4 | 8.4 | 0.7381 |
| A, C | B, D, E, F | 2.2 | 4.2 | 8.2 | 0.7921 |
| A, B, C | D, E, F | 0.2 | 6.2 | 6.2 | 0.0645 · minimum |
| A, D | B, C, E, F | 4.2 | 4.2 | 8.2 | 1.5122 |
| A, B, D | C, E, F | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, C, D | B, E, F | 4 | 6.4 | 6 | 1.2917 |
| A, B, C, D | E, F | 2 | 8.4 | 4 | 0.7381 |
| A, E | B, C, D, F | 4 | 4 | 8.4 | 1.4762 |
| A, B, E | C, D, F | 4 | 6 | 6.4 | 1.2917 |
| A, C, E | B, D, F | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, C, E | D, F | 2.2 | 8.2 | 4.2 | 0.7921 |
| A, D, E | B, C, F | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, D, E | C, F | 4.2 | 8.2 | 4.2 | 1.5122 |
| A, C, D, E | B, F | 4 | 8.4 | 4 | 1.4762 |
| A, B, C, D, E | F | 2 | 10.4 | 2 | 1.1923 |
| A, F | B, C, D, E | 4 | 4 | 8.4 | 1.4762 |
| A, B, F | C, D, E | 4 | 6 | 6.4 | 1.2917 |
| A, C, F | B, D, E | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, C, F | D, E | 2.2 | 8.2 | 4.2 | 0.7921 |
| A, D, F | B, C, E | 4.2 | 6.2 | 6.2 | 1.3548 |
| A, B, D, F | C, E | 4.2 | 8.2 | 4.2 | 1.5122 |
| A, C, D, F | B, E | 4 | 8.4 | 4 | 1.4762 |
| A, B, C, D, F | E | 2 | 10.4 | 2 | 1.1923 |
| A, E, F | B, C, D | 4 | 6 | 6.4 | 1.2917 |
| A, B, E, F | C, D | 4 | 8 | 4.4 | 1.4091 |
| A, C, E, F | B, D | 4.2 | 8.2 | 4.2 | 1.5122 |
| A, B, C, E, F | D | 2.2 | 10.2 | 2.2 | 1.2157 |
| A, D, E, F | B, C | 2.2 | 8.2 | 4.2 | 0.7921 |
| A, B, D, E, F | C | 2.2 | 10.2 | 2.2 | 1.2157 |
| A, C, D, E, F | B | 2 | 10.4 | 2 | 1.1923 |
Inspect the exact adjacency matrix
| Node | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 | 0 |
| B | 1 | 0 | 1 | 0 | 0 | 0 |
| C | 1 | 1 | 0 | 0.2 | 0 | 0 |
| D | 0 | 0 | 0.2 | 0 | 1 | 1 |
| E | 0 | 0 | 0 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 1 | 1 | 0 |
Your turn.
Try an answer before opening a hint. Feedback will explain the result, and you can practice again.
Interactive practice is loading. The lesson, worked example, and printable questions remain available below.
View printable practice and solutions
Use these questions when studying without interactive controls. Opening a written solution does not earn progress.
How many unique nontrivial bipartitions does a four-node set have?
Read the solution
There are 8 assignments with the anchor fixed, minus the all-on-one-side assignment: 7.
For the chain A–B = 1, B–C = 2, C–D = 3, what is the cut weight of {A,B} | {C,D}?
Read the solution
The crossing edge has weight two, so the cut weight is 2.
Which pair describes the same unordered bipartition?
- {A,B,C} | empty and {A} | {B,C}
- Every pair of subsets describes the same split.
- {A} | {B,C} and {B,C} | {A}
- {A} | {B,C} and {B} | {A,C}
Read the solution
Swapping the two sides preserves an unordered bipartition.
Does the laboratory’s degree-volume normalized cut compute the manuscript’s normalized stochastic interaction?
- Only when its animation is running.
- No; it teaches enumeration with a different explicit objective.
- Yes; every graph cut is the same information measure.
- Yes; both use the word partition.
Read the solution
The laboratory teaches enumeration and NCut. The manuscript defines a different normalized objective from conditional Gaussian entropies.
Follow the original record
Use the definitions you just practiced to read the project’s own notation, assumptions, and evidence.
The ideas to keep
- Exclude empty sides and represent complementary cuts once.
- Keep raw cut weight, side volume, and normalized-cut score separate.
- The laboratory’s NCut and the manuscript’s normalized information objective use different definitions.
Reading completion is separate from your practice evidence.
Progress is kept in this browser. How learning works