1 Proof Cleanup
1.
2.
Flow on each edge is at least 0 (capacity constraint)
Because cf (p) = min{cf (u,v) : (u,v) is on p}, in the path p, cf (u,v) > 0, so cf (p) > 0. Because f(u,v) = cf (p) or 0, so f(u,v) >= 0.
Flow on each edge is at most the edge capacity (capacity constraint).
When (u, v) not in path p, f(u,v) = 0, because cf (u,v) >= 0,
so f(u,v) <= cf (u,v).
When (u, v) in the path p,
f(u,v) = cf (p) = min{cf (u,v) : (u,v) is on p} <= cf (u,v).
Flow conservation is satisfied.
For vertex not in the augmenting path, entering and leaving flow are both
0, thus the conservation is satisfied.
For vertex in the augmenting path except s and t, the entering and leaving
flow are both cf (p), thus the conservation is satisfied.
The value of the flow is > 0.
Because the flow leaving source s is cf (p) and no flow entering s, sotheflowiscf(p)>0. (cf(p)>0explainedin1).
3.
4.
2. Island Network
Algorithm:
We can construct a bipartite graph as follows.
The two set of vertexes are professors and students. Each pair of professor and student is an edge in the graph.
Compute the maximum matching of this bipartite graph using maximum flow as described in lecture8.
Let f as an empty set, add the edges in the maximum matching to the set f. And for each vertex that is not in the maximum matching, add an edge with this vertex as one endpoint to the set f.
For each edge (P, S) in the set f, we build a network cable from professor P¡¯s house to student S¡¯s house. The size of the set f is the fewest network cables which satisfy the constraints.
Correctness:
Reducing maximum matching to maximum flow is proved in lecture8.
First obviously, according to our construction each vertex has at least 1 edge in set f that contains it. So the condition that each student be able to communicate with at least one professor and each professor be able to communicate with at least one student is satisfied.
Then we prove that the size of set f is the the fewest network cables to satisfy such condition.
Suppose the size of maximum matching is m and the number of vertexes is n (which the number of professors plus the number of students). According to our construction, the size of f is M + (n – 2*M) = n – M.
Now suppose we have a set of edges T with size w that satisfy such condition. So T contains all the vertexes. The graph
Now we take 1 edge from each component, because the edges are from different components, they don¡¯t share common vertex, so they form a matching with size q. The size of this matching must be equal or less than the size of maximum matching.
so, we have n – w <= q <= M, thus w >= n – M.
So to satisfy such condition, we need at least n – M edges. Thus the edge set f we construct in the algorithm which has size n – M achieved the minimum goal.
3 Computer Peripherals
Algorithm:
1. First we use breath first search algorithm to compute the list of ports that each kind of ports can be converted to.
We construct a graph with each port type as a vertex. For each available adapter, if the adapter convert port A to B, then we add an edge from A to B in the graph.
For example 1 in the requirement PDF. The graph has vertexes: USB, ¡°3.5mm audio¡±, ¡°SD slot¡±, Ethernet, parallel. And it has directed edges: USB -> parallel parallel -> Ethernet parallel- > SD slot.
Then for each vertex in the graph, we use breath first search to compute the list of ports that each port can be converted to by 0, 1 or more adapters.
2. Use maximum-flow algorithm to compute the maximum matching between ports and devices.
The bipartite graph is as follows:
The left vertex set is Laptop ports; the right vertex set is devices. If a device D needs port X and port Y can be converted to port X by 0, 1 or more adapters. which is known by step 1, then we add the edge (Y, D) to the bipartite graph.
Now we compute the maximum matching of this bipartite graph by reducing to Maximum Flow as described in lecture 8.
The maximum number of devices we can connect is cardinality of the maximum matching. The devices in the maximum matching is the devices we can connect at the same time.
Correctness:
In step 1, breath first search can let us know if vertex B can be reached from vertex A through 0, 1 or more edges. In this step an edge from X to Y means port X can be converted to port Y. Thus the computation is correct.
In step 2, in our problem, obviously our graph is bipartite. And we have following constraint, a Laptop port can only be connected to 1 device at most, and 1 device can only be connected to 1 port at most. And if a port can connect to a device through 0, 1 or more adapters, an edge will connect them. Thus our problem can be translated to maximum matching problem and can be further reduced to maximum flow problem as described in lecture8.