¿Puedo diseñar un gráfico para encontrar el flujo máximo en el que fuerce al flujo a pasar por un vértice específico "en su totalidad"? Por ejemplo si un vértice obtiene flujo 10, y tiene múltiples aristas de salida, ¿puedo asegurarme de que sólo mueve 10 y no lo separa a 5 y 5 por ejemplo?
Es decir, que sea "por diseño" del gráfico, y no programando así el maxflow algo.
Espero que la pregunta esté lo suficientemente bien definida. Gracias.
Técnicamente, sí, pero no estoy seguro de que esto sea lo que quieres decir: asegúrate de que sólo hay un camino entre la fuente y el sumidero.
Si hay múltiples caminos de este tipo, no se puede hacer esto para cada algoritmo, porque el algoritmo puede hacer movimientos subóptimos (puede empujar a través de sólo una fracción del flujo disponible).
Sin embargo, suponiendo que esté utilizando cualquier algoritmo de rutas de aumento (un enfoque popular), lo primero que intenta el algoritmo es empujar el flujo a través de una sola ruta, por lo que si eso funciona, no dividirá el flujo (hay algunos casos a considerar, pero es posible).
Por último, si las capacidades son enteras, cualquier algoritmo de flujo estándar (que no sea un solucionador de LP) mantendrá todos los flujos como enteros (no itroducirá fracciones). Por tanto, si el flujo máximo desde ese vértice al sumidero es $1$ no se dividirá.
Espero que esto ayude $\ddot\smile$
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.
