Función de flujo de red dividida

No estoy completamente seguro de haber interpretado correctamente todas las nociones, no definidas en la pregunta, pero supongo que la siguiente solución está bien.

Basta probar la pretensión cuando$v_i=1$para cada$i$. Esto nos permitirá dividir el flujo$f$en$v(f)$fluye con valor$1$cada. Luego, dado un valor natural arbitrario$v_i$está con$\sum v_i=v(f)$, dividimos estos$v(f)$sobre$p$grupos formados por$v_1,\dots, v_p$flujos respectivamente, y luego para cada$i$fusionamos flujos de$i$-ésimo grupo en un flujo con valor$v_i$.

Probamos la posibilidad de dividir un flujo$f$en$v(f)$flujos de valor$1$por inducción con respecto a$v(f)>0$. Si$v(f)=1$entonces ponemos$f_1=f$. Supongamos que ya hemos probado la afirmación de$v(f)=p$. Dejar$f$sea ​​cualquier integral factible$s-t$que fluya$N$con$v(f)=p+1$Empezar desde$s$y seguir la corriente$f$(es decir, a lo largo de los bordes$e$tal que$f(e)>0$), restando$1$de$f$en cada borde pasado. Dado que tanto el gráfico$G$y el numero$v(f)$son finitos, solo podemos restar un número finito de$1$'s, por lo que nos quedaremos en algún paso. Desde$\operatorname{netinflow}(f, v)= \operatorname{netoutlow} (f, v)$para todos los vértices$v$en$G$excepto$s$y$t$, y$\operatorname{netinflow}(f, s)=0$, podemos quedarnos solo en el vértice$t$. Entonces tomamos un camino desde$s$a$t$. Este camino dotado de los valores que le restamos, genera naturalmente un flujo integral$f’$de$s$a a$t$con$v(f’)=1$. Poniendo$f’’=f-f’$obtenemos una integral factible$s-t$que fluya$N$con$v(f’)=p$, que se puede dividir en$p$flujos requeridos por la hipótesis de inducción.