Dejemos que $D=(N,A)$ sea un grafo dirigido, y para un arco $e=xy$ definir $h(e)=x$ y $t(e)=y$ . Un flujo es $\mathbf{x}=(x(e_1),\dots,x(e_k))$ con $\sum_{e:t(e)=v}x(e)=\sum_ {e:h(e)=v}x(e)$ para todos $v\in A\backslash \{s,t\}$ . Un ciclo de flujo es un flujo $\mathbf{y}$ en un ciclo dirigido $C$ dado por $y(e)=\epsilon(C)$ si $e\in E(C)$ y $y(e)=0$ en caso contrario, para algún número positivo $\epsilon(C)$ . Un $s-t$ El camino del flujo es un flujo $\mathbf{z}$ en un dirigido $s-t$ camino $P$ con $z(e)=\epsilon(P)$ para $e\in E(P)$ y $y(e)=0$ en caso contrario, para algún número positivo $\epsilon(P)$ . Demostrar que $\mathbf{x}$ siempre puede escribirse como una suma de trayectorias y ciclos de flujo.
La primera parte del problema consistía en demostrar que una circulación, que no es más que un flujo sin fuente ni sumidero, puede escribirse como una suma de ciclos de flujo. Lo hice mediante la matriz de incidencia $A$ de $D$ , mostrando que una circulación debe estar en el espacio nulo de $A$ lo que significa que podemos formar una base de ciclos, y como esta base está formada por vectores con valores 0, -1 o 1, son ciclos de flujo. Sin embargo, no sé cómo aplicar este enfoque en este caso, ya que no se trata del espacio nulo de la matriz de indicación. ¿Se puede adaptar el enfoque? Si no, ¿debería hacer otra cosa? Estoy realmente atascado aquí.
