Skip to content

22.1 Representations of graphs

22.1-1

Given an adjacency-list representation of a directed graph, how long does it take to compute the $\text{out-degree}$ of every vertex? How long does it take to compute the $\text{in-degree}s$?

Since it seems as though the list for the neighbors of each vertex $v$ is just an undecorated list, to find the length of each would take time $O(\text{out-degree}(v))$. So, the total cost will be

$$\sum_{v \in V}O(\text{out-degree}(v)) = O(|E| + |V|).$$

Note that the $|V|$ showing up in the asymptotics is necessary, because it still takes a constant amount of time to know that a list is empty. This time could be reduced to $O(|V|)$ if for each list in the adjacency list representation, we just also stored its length.

To compute the in degree of each vertex, we will have to scan through all of the adjacency lists and keep counters for how many times each vertex has appeared. As in the previous case, the time to scan through all of the adjacency lists takes time $O(|E| + |V|)$.

22.1-2

Give an adjacency-list representation for a complete binary tree on $7$ vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from $1$ to $7$ as in a binary heap.

  • Adjacency-list representation

    $$ \begin{aligned} 1 &: 2 \rightarrow 3 \\ 2 &: 1 \rightarrow 4 \rightarrow 5 \\ 3 &: 1 \rightarrow 6 \rightarrow 7 \\ 4 &: 2 \\ 5 &: 2 \\ 6 &: 3 \\ 7 &: 3. \end{aligned} $$

  • Adjacency-matrix representation

    $$ \begin{pmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ \end{pmatrix}. $$

22.1-3

The transpose of a directed graph $G = (V, E)$ is the graph $G^\text T = (V, E^\text T)$, where $E^\text T = \{ (v, u) \in V \times V: (u, v) \in E \}$. Thus, $G^\text T$ is $G$ with all its edges reversed. Describe efficient algorithms for computing $G^\text T$ from $G$, for both the adjacency-list and adjacency-matrix representations of $G$. Analyze the running times of your algorithms.

  • Adjacency-list representation: For the adjacency list representation, we will maintain an initially empty adjacency list representation of the transpose. Then, we scan through every list in the original graph. If we are in the list corresponding to vertex $v$ and see $u$ as an entry in the list, then we add an entry of $v$ to the list in the transpose graph corresponding to vertex $u$. Since this only requires a scan through all of the lists, it only takes time $O(|E| + |V|)$.
  • Adjacency-matrix representation: to compute the graph transpose, we just take the matrix transpose. This means looking along every entry above the diagonal, and swapping it with the entry that occurs below the diagonal. This takes time $O(|V|^2)$.

22.1-4

Given an adjacency-list representation of a multigraph $G = (V, E)$, describe an $O(V + E)$-time algorithm to compute the adjacency-list representation of the "equivalent" undirected graph $G' = (V, E')$, where $E'$ consists of the edges in $E$ with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.

Create a new adjacency-list $Adj'$ of size $|V|$ and an empty matrix $M$ of size $|V|^2$ first. For each vertex $u$ in the multigraph $G$, we iterably examine each vertex $v$ of $Adj[u]$.

  • If $M(u, v) == \emptyset$, mark $M(u, v)$ as $\text{true}$, then add $v$ to $Adj'[u]$.
  • If $M(u, v) == true$, do nothing.

Since we lookup in the adjacency-list $Adj$ for $|V + E|$ times, the time complexity is $O(V + E)$.

1
2
3
4
5
6
7
8
EQUIVALENT-UNDIRECTED-GRAPH
    let Adj'[1..|V|] be a new adjacency-list
    let M be |V| × |V|
    for each vertex u  G.V
        for each v  Adj[u]
            if M[u, v] == Ø && u != v
                M[u, v] = true
                INSERT(Adj'[u], v)

22.1-5

The square of a directed graph $G = (V, E)$ is the graph $G^2 = (V, E^2)$ such that $(u, v) \in E^2$ if and only if $G$ contains a path with at most two edges between $u$ and $v$. Describe efficient algorithms for computing $G^2$ from $G$ for both the adjacency-list and adjacency-matrix representations of $G$. Analyze the running times of your algorithms.

  • Adjacency-list representation: To compute $G^2$ from the adjacency-list representation $Adj$ of $G$, we perform the following for each $Adj[u]$:

    1
    2
    3
    4
        for each v  Adj[u]
            for each w  Adj[v]
                edge(u, w)  E^2
                INSERT(Adj2[u], w)
    

    where $Adj2$ is the adjacency-list representation of $G^2$. After we have computed $Adj2$, we have to remove any duplicate edges from the lists (there may be more than one two-edge path in $G$ between any two vertices). For every edge in $Adj$ we scan at most $|V|$ vertices, we compute $Adj2$ in time $O(VE)$. Removing duplicate edges is done in $O(V + E)$ as shown in exercise 22.1-4. Thus the total running time is

    $$O(VE) + O(V + E) = O(VE).$$

  • Adjacency-matrix representation: Let $A$ denote the adjacency-matrix representation of $G$. The adjacency-matrix representation of $G^2$ is the square of $A$. Computing $A^2$ can be done in time $O(V^3)$ (and even faster, theoretically; Strassen's algorithm for example will compute $A^2$ in $O(V^{\lg 7})$).

22.1-6

Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$, but there are some exceptions. Show how to determine whether a directed graph $G$ contains a universal sink $-$ a vertex with $\text{in-degree}$ $|V| - 1$ and $\text{out-degree}$ $0$ $-$ in time $O(V)$, given an adjacency matrix for $G$.

We start by observing that if $a_{ij} = 1$, so that $(i, j) \in E$, then vertex $i$ cannot be a universal sink, for it has an outgoing edge. Thus, if row $i$ contains a $1$, then vertex $i$ cannot be a universal sink. This observation also means that if there is a $\text{self-loop}(i, i)$, then vertex $i$ is not a universal sink. Now suppose that $a_{ij} = 0$, so that $(i, j) \notin E$, and also that $i \ne j$. Then vertex $j$ cannot be a universal sink, for either its $\text{in-degree}$ must be strictly less than $|V| - 1$ or it has a self-loop. Thus if column $j$ contains a $0$ in any position other than the diagonal entry $(j, j)$, then vertex $j$ cannot be a universal sink.

Using the above observations, the following procedure returns $\text{TRUE}$ if vertex $k$ is a universal sink, and $\text{FALSE}$ otherwise. It takes as input a $|V| \times |V|$ adjacency matrix $A = (a_{ij})$.

1
2
3
4
5
6
7
8
9
IS-SINK(A, k)
    let A be |V| × |V|
    for j = 1 to |V|      // Check for a 1 in row k
        if a[k, j] == 1
            return false
    for i = 1 to |V|      // Check for an off-diagonal 0 in column k
        if a[i, k] == 0 and i != k
            return false
    return true

Because this procedure runs in $O(V)$ time, we may call it only $O(1)$ times in order to achieve our $O(V)$-time bound for determining whether directed graph $G$ contains a universal sink.

Observe also that a directed graph can have at most one universal sink. This property holds because if vertex $j$ is a universal sink, then we would have $(i, j) \in E$ for all $i \ne j$ and so no other vertex $i$ could be a universal sink.

The following procedure takes an adjacency matrix $A$ as input and returns either a message that there is no universal sink or a message containing the identity of the universal sink. It works by eliminating all but one vertex as a potential universal sink and then checking the remaining candidate vertex by a single call to $\text{IS-SINK}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
UNIVERSAL-SINK(A)
    let A be |V| × |V|
    i = j = 1
    while i  |V| and j  |V|
        if a[i, j] == 1
            i = i + 1
        else j = j + 1
    if i > |V|
        return "there is no universal sink"
    else if IS-SINK(A, i) = false
        return "there is no universal sink"
    else return i "is a universal sink"

$\text{UNIVERSAL-SINK}$ walks through the adjacency matrix, starting at the upper left corner and always moving either right or down by one position, depending on whether the current entry $a_{ij}$ it is examining is $0$ or $1$. It stops once either $i$ or $j$ exceeds $|V|$.

To understand why $\text{UNIVERSAL-SINK}$ works, we need to show that after the while loop terminates, the only vertex that might be a universal sink is vertex $i$. The call to $\text{IS-SINK}$ then determines whether vertex $i$ is indeed a universal sink.

Let us fix $i$ and $j$ to be values of these variables at the termination of the while loop. We claim that every vertex $k$ such that $1 \le k < i$ cannot be a universal sink. That is because the way that $i$ achieved its final value at loop termination was by finding a $1$ in each row $k$ for which $1 \le k < i$. As we observed above, any vertex $k$ whose row contains a $1$ cannot be a universal sink.

If $i > |V|$ at loop termination, then we have eliminated all vertices from consid- eration, and so there is no universal sink. If, on the other hand, $i \le |V|$ at loop termination, we need to show that every vertex $k$ such that $i < k \le |V|$ cannot be a universal sink. If $i \le |V|$ at loop termination, then the while loop terminated because $j > |V|$. That means that we found a $0$ in every column. Recall our earlier observation that if column $k$ contains a $0$ in an off-diagonal position, then vertex $k$ cannot be a universal sink. Since we found a $0$ in every column, we found a $0$ in every column $k$ such that $i < k \le |V|$. Moreover, we never examined any matrix entries in rows greater than $i$, and so we never examined the diagonal entry in any column $k$ such that $i < k \le |V|$. Therefore, all the $0$s that we found in columns $k$ such that $i < k \le |V|$ were off-diagonal. We conclude that every vertex $k$ such that $i < k \le |V|$ cannot be a universal sink.

Thus, we have shown that every vertex less than $i$ and every vertex greater than $i$ cannot be a universal sink. The only remaining possibility is that vertex $i$ might be a universal sink, and the call to $\text{IS-SINK}$ checks whether it is.

To see that $\text{UNIVERSAL-SINK}$ runs in $O(V)$ time, observe that either $i$ or $j$ is incremented in each iteration of the while loop. Thus, the while loop makes at most $2|V| - 1$ iterations. Each iteration takes $O(1)$ time, for a total while loop time of $O(V)$ and, combined with the $O(V)$-time call to $\text{IS-SINK}$, we get a total running time of $O(V)$.

22.1-7

The incidence matrix of a directed graph $G = (V, E)$ with no self-loops is a $|V| \times |E|$ matrix $B = (b_{ij})$ such that

$$ b_{ij} = \begin{cases} -1 & \text{if edge $j$ leaves vertex $i$}, \\ 1 & \text{if edge $j$ enters vertex $i$}, \\ 0 & \text{otherwise}. \end{cases} $$

Describe what the entries of the matrix product $BB^\text T$ represent, where $B^\text T$ is the transpose of $B$.

$$BB^\text T(i, j) = \sum\limits_{e\in E}b_{ie} b_{ej}^\text T = \sum\limits_{e\in E}b_{ie}b_{je}.$$

  • If $i = j$, then $b_{ie} b_{je} = 1$ (it is $1 \cdot 1$ or $(-1) \cdot (-1)$) whenever $e$ enters or leaves vertex $i$, and $0$ otherwise.
  • If $i \ne j$, then $b_{ie} b_{je} = -1$ when $e = (i, j)$ or $e = (j, i)$, and $0$ otherwise.

Thus,

$$ BB^\text T(i, j) = \begin{cases} \text{degree of $i$ = in-degree + out-degree} & \text{if $i = j$}, \\ \text{$-$(\# of edges connecting $i$ and $j$)} & \text{if $i \ne j$}. \end{cases} $$

22.1-8

Suppose that instead of a linked list, each array entry $Adj[u]$ is a hash table containing the vertices $v$ for which $(u, v) \in E$. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in the graph? What disadvantages does this scheme have? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table?

The expected loopup time is $O(1)$, but in the worst case it could take $O(|V|)$. If we first sorted vertices in each adjacency list then we could perform a binary search so that the worst case lookup time is $O(\lg |V|)$, but this has the disadvantage of having a much worse expected lookup time.