Explicación del teorema de Max-flow-min-cut detrás de la prueba

Question

Explicación del teorema de Max-flow-min-cut detrás de la prueba

Matemáticas
Teoría de grafos
flujo de red

asdf

El teorema establece lo siguiente:

En cualquier red $(G, s, t, c)$ $(G$ es un grafo dirigido, $s$ es la fuente, $t$ es el fregadero, $c$ son las capacidades $)$ tenemos $\sup\{ v(f) : f$ es un flujo factible $\} = \min \{ c(S, T) : (S, T)$ es un corte }$

Además, se alcanza el supremo

Se adjunta la prueba en las notas de clase.

El problema comienza en "Repitiendo esto para cada borde, encontramos una subsecuencia de flujos con $v(f_i) \rightarrow M$ tal que $f_i(x,y)$ converge para cada..."

si elegimos $1$ borde, podemos encontrar esta subsecuencia convergente, por ejemplo, encontrando una secuencia monótona y usando resultados de análisis estándar. Pero cuando elegimos el segundo borde, ¿cómo garantizamos que la secuencia de flujos converge para ambos bordes?

gracias de antemano

frgt

¿Qué libro es ese?

Respuestas (1)

Explicación del teorema de Max-flow-min-cut detrás de la prueba

NS · Answer 1

El truco es un análisis estándar:

Dejar $f_n(x_1y_1)$ y $f_n(x_2y_2)$ ser dos secuencias. Entonces podemos encontrar una subsecuencia $f_{k_n}(x_1y_1)$ que es convergente. A continuación, en lugar de mirar $f_n(x_2y_2)$ , mira la subsecuencia $f_{k_n}(x_2y_2)$ . Esta es acotada, por lo que tiene una subsecuencia convergente $f_{l_n}(x_2y_2)$ .

Ahora, desde $f_{l_n}(x_1y_1)$ es una subsecuencia de $f_{k_n}(x_1y_1)$ es convergente.

Nota Este es en realidad un argumento sobre la compatibilidad. En $\mathbb R^d$ un conjunto es compacto si es cerrado y acotado. Así, por acotación, la sucesión

(F_{norte} (X_{1} y_{1}), F_{norte} (X_{2} y_{2}), . . ., F_{norte} (X_{d} y_{d})

$(f_n(x_1y_1), f_n(x_2y_2),..., f_n(x_dy_d)$ tiene una subsecuencia convergente en alguna bola cerrada en

R^{d}

$\mathbb R^d$ .

Explicación del teorema de Max-flow-min-cut detrás de la prueba

asdf

frgt

Respuestas (1)

NS

asdf

Flujo máximo en gráfico no dirigido con bordes restringidos

Función de flujo de red dividida

Pasar de la intuición abstracta a la prueba formal

Gráfico Residual (Max - Flow) - Intuición y corrección

¿Cuál es la intuición detrás del aumento de caminos en gráficos residuales? (Ford-Fulkerson)

¿Por qué la homología no puede distinguir entre gráficos planos y no planos?

¿Cómo podemos formalizar la noción de la cara de un gráfico plano?

Origen del término "grafo plano"

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Número cromático total de ciclos