Number of edges in acyclic flow
The graph in this post are simple graphs with unit edge capacity.
Let be a graph with vertices and edges, then an acyclic integer flow of value saturates edges.
Everything here is in the Karger and Levine’s paper[???], I’m writing this down for my own sake.
Let to be the distance of the shortest path between and . Let to be the value of a --flow, then and .
Let to be the set of vertices with distance exactly from . The maximum flow is clearly bounded by , as all flows has to go in between the two levels and the maximum number of edges in between happens when it is a complete bipartite graph. Notice in order to maximize this value, we have . Hence . Similarly, we can also distribute the number of edges in between every two partitions, and get .
If we take shortest augmenting path successively in the residual graph to find a flow of value , then we saturate edges.
, thus . If we take the shortest path successively, we have the number of edges we use in each augmenting path is
For the above theorem, one might ask what happens if we use inequality instead. Then we get the sum of the length of all the augmenting paths we ever route is , pretty neat.
Let be an acyclic flow of value in . Remove all edges outside , and let the remaining graph be . Consider use shortest augmenting path algorithm sending a flow of value in . Notice this would produce . Thus this shows has edges.
Let be a simple graph on vertices. There exist -edge disjoint paths, such that the shortest paths has total of edges for all .
There exist -edge disjoint paths with total length . The average length is . The shortest paths has total length .