Graph theory

Правка en2, от Ahmed_Hussein_Karam, 2017-06-06 00:43:43

According to this wikipedia link, under the title "Success probability of the contraction algorithm":
Number of possible cuts in a graph is 2^(n-1)-1, while maximum number of minimum cuts is nC2, where n is number of vertices.
My question:
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a (candidate) minimum cut?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Ahmed_Hussein_Karam 2017-06-06 00:43:43 10 Tiny change: 'is 2^(n-1) — 1, while m' -> 'is 2^(n-1)-1, while m'
en1 Английский Ahmed_Hussein_Karam 2017-06-06 00:43:03 486 Initial revision (published)