EECS 340/454: Algorithms
Assignment 7: Graph Algorithms
¨
Problem 1
There are n basketball teams in the world. The ranking of these teams from the previous year is
available. This year, some of these n teams played against each other and the winner of each game
was determined. There were m games in total. The International Basketball Association wants to
introduce a new performance criterion, called “domination factor”, defined as follows: Team i is
said to “dominate” team j if we can find a chain of games such that j was beaten by a team that
was beaten by a team that was beaten by a team ... that was beaten by i (observe that, according
to this definition, domination can be bi-directional, i.e., i and j can dominate each other). Then,
for each team i, the domination factor zi
is defined as the rank of the best team (that is, the highest
ranked team according to last year’s rankings) that is dominated by team i.
(a) Describe an O(m + n) time algorithm to compute the domination factor for all the n teams.
(Hint: Use Depth-First-Search)
(b) Prove that your algorithm is correct.
Problem 2
Prove or disprove the following statements:
(a) Let G = (V, E) be a directed graph. For any uv ∈ E, if some run of Depth-First-Search
(DFS) on G results in v.f > u.f, then uv must be on a cycle.
(b) Consider any run of DFS on a directed graph G = (V, E). For any edge uv ∈ E, if there is a
path from v to u in G, then uv cannot be a cross edge.
Problem 3 - Removed
This problem was removed because Dijkstra’s algorithm has not yet been taught.
Problem 4
Please upload evidence of completion of course evaluation (a screenshot of the confirmation page
will suffice). Note: This is 20% of assignment grade.
