Problem Set 4

Given an adjacency-list representation of a directed graph, where each vertex maintains an array of its outgoing edges (but *not* its incoming edges), how long does it take, in the worst case, to compute the in-degree of a given vertex? As usual, we use 𝑛 and 𝑚 to denote the number of vertices and edges, respectively, of the given graph. Also, let 𝑘 denote the maximum in-degree of a vertex. (Recall that the in-degree of a vertex is the number of edges that enter it.)

• Θ⁡(𝑛)
• Cannot determine from the given information
• Θ⁡(𝑘)
• Θ⁡(𝑚)

ANSWER: We must read all edges (or the edge not read may contribute to a in-degree count of the given vertex), so we have the time lowered bounded by 𝑚.

We can compute the in-degree by just reading all edges and keep track of the in-degree count, so we have the time upper bounded by 𝑚.

Therefore the solution is Θ⁡(𝑚). Option 4 is correct.

Consider the following problem: given an undirected graph 𝐺 with 𝑛 vertices and 𝑚 edges, and two vertices 𝑠 and 𝑡, does there exist at least one 𝑠 −𝑡 path?

If 𝐺 is given in its adjacency list representation, then the above problem can be solved in 𝑂⁢(𝑚 +𝑛) time, using BFS or DFS. (Make sure you see why this is true.)

Suppose instead that 𝐺 is given in its adjacency *matrix* representation. What running time is required, in the worst case, to solve the computational problem stated above? (Assume that 𝐺 has no parallel edges.)

• Θ⁢(𝑛 ∗𝑚)
• Θ⁢(𝑚 +𝑛⁢log⁡𝑛)
• Θ⁡(𝑛2)
• Θ⁢(𝑚 +𝑛)

ANSWER: Option 3 is correct. For the lower bound, every time we want to find the edges adjacent to a given vertex 𝑢, we have to traverse the whole array, which is of length 𝑛; this happens for all the vertices. One easy way to prove the upper bound is to first build an adjacency list representation in Θ⁡(𝑛2) time, with a single scan over the given adjacency matrix and then run BFS or DFS as in the video lectures.

This problem explores the relationship between two definitions about graph distances. In this problem, we consider only graphs that are undirected and connected. The diameter of a graph is the maximum, over all choices of vertices 𝑠 and 𝑡, of the shortest-path distance between 𝑠 and 𝑡. (Recall the shortest-path distance between 𝑠 and 𝑡 is the fewest number of edges in an 𝑠 −𝑡 path.)

Next, for a vertex 𝑠, let 𝑙⁡(𝑠) denote the maximum, over all vertices 𝑡, of the shortest-path distance between 𝑠 and 𝑡. The radius of a graph is the minimum of 𝑙⁡(𝑠) over all choices of the vertex 𝑠.

Which of the following inequalities always hold (i.e., in every undirected connected graph) for the radius 𝑟 and the diameter 𝑑? [Select all that apply.]

• 𝑟 ≤𝑑2
• 𝑟 ≤𝑑
• 𝑟 ≥𝑑
• 𝑟 ≥𝑑2

ANSWER: We need some definitions:

• Distance: The distance between two vertices 𝑢 and 𝑣 in a graph 𝐺 is is defined as the length of a shortest path from 𝑢 to 𝑣 and is denoted by 𝑑⁡(𝑢,𝑣). Distance on graphs is a metric and defines a metric space. Mathematically, 𝑑 :𝑉⁡(𝐺) ×𝑉⁡(𝐺) →ℤ∗ ∪0, where 𝑉 is the vertex set and ℤ∗ the set of positive integers.

Distance rules:

1. 𝑑⁡(𝑢,𝑣) ≥0 and 𝑑⁡(𝑢,𝑣) =0 ⟺ 𝑢 =𝑣
2. 𝑑⁡(𝑢,𝑣) =𝑑⁡(𝑣,𝑢)
3. 𝑑⁡(𝑢,𝑤) ≤𝑑⁡(𝑢,𝑣) +𝑑⁡(𝑣,𝑤)

1 and 2 should be obvious. 3 follows from the Triangle inequaity; we can use this property because distance on graphs is a metric.

• Eccentricity: Maximum distance between a given vertex 𝑣 to any other vertex 𝑢 in the graph. 𝑒⁡(𝑣) =𝑚⁢𝑎⁢𝑥⁡{𝑑⁡(𝑢,𝑣) | 𝑢,𝑣 ∈𝐺}

• Diameter: Maximum eccentricity. 𝑑⁢𝑖⁢𝑎⁢𝑚⁡(𝐺) =𝑚⁡𝑎⁢𝑥⁡{𝑒⁡(𝑣) | 𝑣 ∈𝐺}

• Radius: Minumum eccentricity. 𝑟⁢𝑎⁢𝑑⁡(𝐺) =𝑚⁢𝑖⁢𝑛⁡{𝑒⁡(𝑣) | 𝑣 ∈𝐺}

Example:

𝑑⁡𝑖⁢𝑎⁢𝑚⁡(𝐺) =3,𝑟⁢𝑎⁢𝑑⁡(𝐺) =2

• Center: The set of all such vertices for which 𝑒⁡(𝑣) =𝑟⁢𝑎⁢𝑑⁡(𝐺) make up the center of 𝐺.
• Periphery: The set of all such vertices for which 𝑒⁡(𝑣) =𝑑⁢𝑖⁢𝑎⁢𝑚⁡(𝐺) make up the periphery of 𝐺.

Now, we will prove that 𝑟⁢𝑎⁢𝑑⁡(𝐺) ≤𝑑⁡𝑖⁢𝑎⁢𝑚⁡(𝐺) ≤2 ∗𝑟⁢𝑎⁢𝑑⁡(𝐺). The first part is obvious from the definitions of radius and diameter. For the second part, consider two vertices 𝑢 and 𝑣 on the periphery. Consider a vertex 𝑤 in the center. By distance law:

Therefore, options 2 and 4 are correct.

Consider our algorithm for computing a topological ordering that is based on depth-first search (i.e., NOT the “straightforward solution”). Suppose we run this algorithm on a graph 𝐺 that is NOT directed acyclic. Obviously it won’t compute a topological order (since none exist). Does it compute an ordering that minimizes the number of edges that go backward?

For example, consider the four-node graph with the six directed edges (𝑠,𝑣),(𝑠,𝑤),(𝑣,𝑤),(𝑣,𝑡),(𝑤,𝑡),(𝑡,𝑠). Suppose the vertices are ordered 𝑠,𝑣,𝑤,𝑡. Then there is one backwards arc, the (𝑡,𝑠) arc. No ordering of the vertices has zero backwards arcs, and some have more than one.

• Sometimes yes, sometimes no
• Never
• If and only if the graph is a directed cycle
• Always

ANSWER: The graph in question is shown below:

If we run DFS from vertex 𝑠, there is only one backward edge (𝑡,𝑠). But if we run DFS from 𝑡, the ordering is 𝑤,𝑣,𝑠,𝑡, with all the edges pointing backward. Thus, option 1 is coorect.

On adding one extra edge to a directed graph 𝐺, the number of strongly connected components…?

• …never decreases by more than 1 (no matter what 𝐺 is)
• …never decreases (no matter what 𝐺 is)
• …could remain the same (for some graphs 𝐺)
• …will definitely not change (no matter what 𝐺 is)

ANSWER: Consider the directed path 1 →2 →3 →4; there are four SCCs, one for each vertex. If we add an edge 4 →1, then the four SCCs merge into one; therefore, options 1, 2 and 4 are incorrect. On the other hand, adding edge 1 →2 doesn’t change anything. Thus, option 3 is correct.