Description
Q1. Determine if the following statements are true or false. If true, give
a brief explanation. If false give a counterexample. (10 points)
(a) For a flow network, there always exists a maximum flow that doesn’t include a cycle
containing positive flow.
(b) If you have non-integer edge capacities, then you cannot have an integer max-flow value.
(c) Suppose the maximum s-t flow of a graph has value f. Now we increase the capacity of
every edge by 1. Then the maximum s-t flow in this modified graph will have a value of at most f
+ 1.
(d) If all edge capacities are multiplied by a positive number k , then the min-cut remains
unchanged.
Q2. A tourist group needs to convert all of their USD into various
international currencies.There are n tourists t1,t2, …,tn and m
currencies c1,c2, …,cm. Each tourist tk has Fk Dollars to convert.
For
each currency cj , the bank can convert at most Bj Dollars to cj.Tourist
tk is willing to trade at most Skj of their Dollars for currency cj. (For
example, a tourist with 1000 dollars might be willing to convert up to
300 of their USD for Rupees, up to 500 of their USD for Japanese Yen,
and up to 400 of their USD for Euros).
Assume that all tourists give
their requests to the bank at the same time. Design an algorithm that
the bank can use to determine whether all requests can be satisfied.
To do this, construct and draw a network flow graph, with appropriate
source and sink nodes, and edge capacities.
Prove your algorithm is correct by making an if-and-only-if claim (10
points)
Q3. You are given a collection of n points U={u1,…,un} in the plane,
each of which is the location of a cell-phone user. You are also given
the locations of m cell-phone towers,C={c1,…,cm}. A cell-phone user
can connect to a tower if it is within distance ∆ of the tower.
For the
sake of fault-tolerance each cell-phone user must be connected to
at least three different towers. For each tower ci you are given the
maximum number of users, mi that can connect to this tower. Give a
polynomial time algorithm, which determines whether it is possible to
assign all the cell-phone users to towers, subject to these constraints.
Prove your algorithm is correct by making an if-and-only-if claim. (You
may assume you have a function that returns the distance between
any two points in O(1) time.) (10 points)
Q4. You are given a directed graph which after a few iterations of
Ford-Fulkerson has the following flow. The labeling of edges indicate
flow/capacity: (15 points)
a) Draw the corresponding residual graph.
b) Is this a max flow? If yes, indicate why. If no, find max flow.
c) What is the min-cut?
Q5. USC has resumed in-person education after a one-year break,
with k on-site courses available this term, labeled c1
through ck
.
Additionally, there are n students, labeled s1
to sn, attending these k
courses. It’s possible for a student to attend multiple on-site courses,
and each course will have a variety of students enrolled. (20 points)
(a) Each student sj wishes to enroll in a specific group pj of the k
available courses, with the condition that each must enroll in at least
m courses to qualify as a full-time student (where pj is greater than or
equal to m). Furthermore, every course ci can only accommodate a
maximum of qi students. The task for the school’s administration is to
verify whether every student can register as a full-time student under
these conditions. Propose an algorithm to assess this scenario. Prove
your algorithm is correct by making an if-and-only-if claim.
(b) Assuming a viable solution is found for part (a) where each
student is enrolled in exactly m courses, there arises a need for a
student representative for each course from among the enrolled
students. However, any single student can represent at most r (where
r is less than m) courses in which they are enrolled. Develop an
algorithm to check whether it is possible to appoint such
representatives, building on the solution from part (a) as a foundation.
Prove your algorithm is correct by making an if-and-only-if claim.
Q6. Given the below graph solve the below questions using scaled version of
Ford-Fulkerson. (15 points)
a) Give the Δ and path selected at each iteration.
b) Draw the final network graph and the residual graph
c) Find the maxflow and mincut
Q7:The following graph G has labeled nodes and edges between
them. Each edge is labeled with its capacity. (10 points)
(a) Draw the final residual graph Gf using the Ford-Fulkerson
algorithm corresponding to the max flow. Please do NOT show all
intermediate steps.
(b) What is the max-flow value?
(c) What is the min-cut?
Q8. You are provided with a flow network where each edge has a
capacity of one. This network is represented by a directed graph G =
(V, E), including a source node s and a target node t. Additionally, you
are given a positive integer k. The objective is to remove k edges to
achieve the greatest possible reduction in the maximum flow from s
to t in G.
Your task is to identify a subset of edges F within E, where
the size of F equals k, and removing these edges from G results in a
new graph G’ = (V, E-F) where the maximum flow from s to t is
minimized. Propose a polynomial-time strategy to address this issue.
Furthermore, consider if the capacities of the edges are greater than
one, and discuss whether your strategy still ensures the lowest
possible maximum flow. (20 points)
