Using the definition of a flow, prove that if (u, v) ∉ E and (v, u) ∉ E then f(u, v) = f(v, u) = 0.
f(u,v) <= c(u,v)
f(u,v) + f(v, u) = 0
c(u,v) = 0So f(u,v) = f(v,u) = 0
Prove that for any vertex v other than the source or sink, the total positive flow entering v must equal the total positive flow leaving v.
Capacity constraint: For all u, v ∈ V, we require f(u, v) <= c(u, v)
Skew Symmetry: For all u, v ∈ V, we require f(u, v) <= -f(u, v)
Flow conservation: For all u, v ∈ V – {s, t}, we require Σ f(u, v) = 0
Extend the flow properties and definitions to the multiple-source, multiple-sink problem. Show that any flow in a multiple-source, multiple-sink flow network corresponds to a flow of identical value in the single-source, single-sink network obtained by adding a supersource and a supersink, and vice versa.
In Figure 26.2, we add a supersource s and add a directed edge (s, si) with capacity c(s, si) = ∞ for each i = 1, 2, . . . , m. We also create a new supersink t and add a directed edge (ti, t) with capacity c(ti, t) = ∞ for each i = 1, 2, . . . , n. The single source s simply provides as much flow as desired for the multiple sources si, and the single sink t likewise consumes as much flow as desired for the multiple sinks ti.
Because the virutal edges of s and t can consume as much flows as they want, they don't influence the actual edges.
Prove Lemma 26.1.
Pretty obvious, several vertices make up a set. Apply each f on on vertices and combine them.
For the flow network G = (V, E) and flow f shown in Figure 26.1(b), find a pair of subsets X, Y for all u, v ∈ V. If f1 and f2 are flows in G, which of the three flow properties must the flow sum f1 + f2 satisfy, and which might it violate? V for which f(X, Y) = - f(V - X, Y). Then, find a pair of subsets X, Y ∈ V for which f (X, Y) ≠ - f(V - X, Y).
X = {v1, v2} , Y = {v3} , f(X, Y) = - f(V - X, Y)
X = {s} , Y = {t} , f(X, Y) ≠ - f(V - X, Y)
Given a flow network G = (V,E),let f1 and f2 be functions from V×V to R.The flow sum f1 + f2 is the function from V × V to R defined by
(26.4) (f1+f2)(u,v) = f1(u,v) + f2(u,v)
for all u, v ∈ V. If f1 and f2 are flows in G, which of the three flow properties must the flow sum f1 + f2 satisfy, and which might it violate?
Flow conservation, may violate Capacity constraint
Let f be a flow in a network, and let α be a real number. The scalar flow product, denoted α f, is a function from V × V to **R defined by
(αf)(u, v) = α · f (u, v).
Prove that the flows in a network form a convex set. That is, show that if f1 and f2 are flows, thensoisαf1 +(1-α)f2 forallαintherange0≤α≤1.
UNSOLVED
State the maximum-flow problem as a linear-programming problem.
Haven't focus on linear-programming yet.
Professor Adam has two children who, unfortunately, dislike each other. The problem is so severe that not only do they refuse to walk to school together, but in fact each one refuses to walk on any block that the other child has stepped on that day. The children have no problem with their paths crossing at a corner. Fortunately both the professor's house and the school are on corners, but beyond that he is not sure if it is going to be possible to send both of his children to the same school. The professor has a map of his town. Show how to formulate the problem of determining if both his children can go to the same school as a maximum-flow problem.
Each edge has weight 1, to see if the max flow is bigger than 1.
Follow @louis1992 on github to help finish this task.