Search every possible split
Change a small graph and compare every eligible bipartition using an explicit normalized-cut objective.
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 |
Learn the ideas behind this lab.
Follow a worked example, practice on your own, and return to the original project sources.
Progress is kept in this browser. How learning works