En un red de transporte el algoritmo Ford Fulkerson y otros se utilizan a menudo para determinar el caudal máximo. Para empezar, ¿cómo sabemos que existe un caudal que es un caudal máximo?
El libro de Van Lint "A course in combinatorics" del que estoy leyendo dice que el flujo máximo existe por " razones de continuidad ". No lo entiendo.
Tienes algunas suposiciones con las que trabajar aquí que garantizan un flujo máximo (el flujo es la cantidad, puede haber muchas distribuciones de ese flujo a través del gráfico que funcionen). Por un lado, en teoría de grafos es típico suponer que el grafo es finito a menos que se indique lo contrario (esto es común pero no universal, así que comprueba las convenciones de tu autor; esperemos que te lo hayan indicado). Además, como se trata de un grafo de flujo, eso significa que hay una fuente y un sumidero. La razón específica por la que se refiere a razones de continuidad es que se puede representar el espacio de los flujos posibles (los que se ajustan a las restricciones del problema, máximo o no), como un subconjunto convexo de $(\mathbb{R}^+)^{|E|}$ donde $|E|$ denota el número de aristas del gráfico y es el "exponente" de $\mathbb{R}^+$ . Porque ese conjunto es un subconjunto convexo de $\mathbb{R}^{|E|}$ En este caso, se utilizan teoremas de análisis para demostrar que existe un punto en su frontera de "distancia" máxima (la distancia se mide por la métrica "taxicab", que es la suma de los valores absolutos de los cambios en cada variable, no la distancia euclidiana) desde el origen (el flujo máximo está limitado por las restricciones en las aristas y la finitud del grafo).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
