 |
 |
19 of 32 |  |
 |
 |
MIT
A Counting Theorem
l
Theorem: for any a ³ 1,
there are at
most n²
a
cuts that are a-minimum
l
Tight for half-integer a
l
Recent tightening:
l
Conjecture cycle is tight
»
but 4-clique has more (4/3)-min
-cuts [NI]
[
]
[
]
÷
ø
ö
ç
è
æ
-
+
a
a
a
2
2
1
2
1
n