¿El método codicioso garantiza el flujo máximo en un árbol dirigido?

Considere un árbol dirigido$G$con un nodo raíz$s$. Dejar$s$ser el nodo fuente de$G$y sus hojas son los nodos sumideros (llame a estas hojas$t$). (Y, por supuesto, los bordes tienen sus respectivas capacidades como cualquier problema de flujo de red).

Notaciones utilizadas

$s$- fuente
$t$- hundir
$f(e)$- flujo en el borde$e$
$c(e)$- capacidad en el borde$e$
$v(f)$- valor del flujo

Algoritmo codicioso

• Empezar con$f(e) = 0$para todos los bordes en$G$.
• Encuentra un$s-t$camino donde para cada borde$e$,$f(e) < c(e)$, y aumente el flujo a lo largo de este camino hasta que uno de los bordes de este camino alcance su capacidad. Rehacer este paso para otro$s-t$camino donde$f(e) < c(e)$para todos los bordes en el camino. Vuelva a hacer hasta que no queden más rutas para aumentar el flujo.

Demuestre que este algoritmo codicioso calcula con éxito el flujo máximo de$G$, o mostrar un contraejemplo.

Intentar

Originalmente creí que este problema era falso, ya que encontré algunos ejemplos de algoritmos codiciosos que se utilizan para demostrar la incorrección. Pero después de pensarlo, me di cuenta de que me perdí un detalle crucial que lo diferencia de cualquier otro intento de flujo máximo codicioso de gráficos, ya que este es un árbol . Creo en este mismo hecho de que es un árbol: ¡no hay ciclos! – hace la diferencia para permitir que este algoritmo funcione.

La razón por la que esto funciona parece bastante obvia al principio, pero me cuesta convencerme de ello.

Al elegir una ruta arbitraria desde el nodo raíz hasta una hoja y aumentar el flujo, aunque esto puede afectar la cantidad de flujo que se puede enviar a lo largo de una ruta similar.$s-t$ruta que comparte algunos bordes desde el nivel superior, no debería alterar el valor de flujo general enviado a los sumideros, ya que cualquier flujo que ingrese debe llegar al sumidero (hojas) (Este detalle es más aparente si miro el árbol usando su definición recursiva usando subárbol nodos). Dado que cada nodo tiene solo uno en grado, solo recibe flujo de una sola fuente, por lo que simplemente puede distribuirlo a sus hijos (si los hay) libremente sin tener que concentrarse mucho para maximizar el flujo en gráficos generales. Simplemente podemos repetir este proceso hasta que los bordes, ya sea en el nivel superior en el origen o en cualquier otro lugar de la ruta, estén llenos a su máxima capacidad.

Creo que tengo los conceptos básicos para comenzar la prueba, pero tengo problemas para formalizarla (no estoy seguro de cómo aplicar su prueba de algoritmo codicioso habitual aquí, ya que técnicamente no hay "conflicto" per se ...). Pero, de nuevo, podría estar equivocado y perderme un contraejemplo.

Cualquier entrada sería apreciada. Gracias.