Para un gráfico de flujo de red dado, ¿es cierto que tiene exponencialmente muchos cortes mínimos? Si es cierto, ¿cómo es eso?

Answer 1

En el peor de los casos, el número de cortes mínimos [matemáticos] st [/ matemáticos] puede ser exponencial.

Por ejemplo, considere una red de flujo con vértices [matemática] V = \ {s, t, v_1, v_2, \ dots, v_n \} [/ math]. Por cada [matemática] i \ in \ {1,2, \ puntos, n \} [/ matemática], cree una ventaja desde [matemática] s [/ matemática] a [matemática] v_i [/ ​​matemática] de capacidad [matemática ] 1 [/ matemáticas]. Por cada [matemática] i \ in \ {1,2, \ puntos, n \} [/ matemática], cree una ventaja desde [matemática] v_i [/ ​​matemática] a [matemática] t [/ matemática] de capacidad [matemática ] 1 [/ matemáticas]. Aquí, el flujo máximo [math] st [/ math] es [math] n [/ math] y, por lo tanto, el corte mínimo también tiene capacidad [math] n [/ math]. Tome cualquier subconjunto [math] U \ subseteq \ {v_1, v_2, \ dots, v_n \} [/ math], deje que [math] S = \ {s \} \ cup U, T = V \ setminus S [/ math ] Cualquiera de estos [math] (S, T) [/ math] forma un corte mínimo, por lo que hay [math] 2 ^ n = 2 ^ {| V | -2} [/ math] cortes mínimos, que es exponencial.

Por supuesto, este es el peor de los casos, y es fácil construir redes de flujo con cortes mínimos únicos.