 Exercises 2.1-1

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

The out-degree of a vertex is the number of edges leaving it. By definition an edge consists of a pair of vertices (note: Can be self-loops) and for the directed graph G = (V, E) consists of an array of adjacency of |V| lists such as adjacency-list [u] u Î V. That means the time taken to compute the out-degree will be equal to the time it takes to search through the adjacency-lists for that vertex. If the adjacency-lists have n vertices then the time taken will be the same as the search time for binary tree O(n). (See textbook page 253 for explanation).

Similarly the time takes to compute the in-degree is O(n)

Redo exercise 2.1-1:

Reference: COMP510 Fall 2005: HW 9 Collaboration

To compute for the Out-degree of every vertex, O(|E|+|V|)

To compute for the In-Dgree of every vertex, O(|V|+|E|)

Definitions: Directed Graph Adjacency-List Representation of a Directed Graph

The out-degree of a vertex is the number of its out-edges or number of edges leaving it.  The in-dgree of a vertex is the number of its in-edges or number of edges entering it.

Demystified Explanation:

To calculate the out degree of any one, single, vertex, you must go through at most E edges (where E is the number of edges).  So this is O(E).

To calculate the out degree of every vertex (all of them), you will still go through at most E edges, since the total number of edges was E.  But now, you must also iterate once through every vertex...since you want to look at each of them in turn and count how many edges go out from them.  This iterating through the vertices is O(V) (where V is the total number of vertices).  Putting this together, it gives O(V + E) to calculate the out degree of every vertex.

Calculating the in-degree will be very similar.  Again, the algorithm would go through every vertex (O(V)) and run through the adjacency lists (O(E)).  For every vertex it finds inside an adjacency list, it will increment that vertice's cooresponding in-degree count.

Example of the way tt might run.

1->2->3

2->2

3->3

So, starting with the first vertex, we run through its adjacency list.  We find vertices 2 and three, so we increment their in-degree counts to 1.

At the next vertex, we run through the adjacency list and get vertex 2.  We increment its in-degree count to become 2 now.

At the third and last vertex, we run through the adjacency list and get vertex 3.  We increment its in-degree count to become 2 now.

So we now have the in-degree counts of all the vertices (0 for vertex 1, 2 for vertex 2, and 2 for vertex 3) And again, we've run through every edge (O(E)), and looked at every vertex (O(V)).  So, O(V + E).

Pseudo-Code Explanation (From a CS Point of View using Algorithms):

Algorithm for out-degree:

1     For each u in V do

2           out-deg[u] = 0

3     For each u in V do

4           For each v in Adj[u] do

5                 out-deg[u] = out-deg[u] + 1 // count # of edges from u

Time for steps 1 and 2 take O(|V|) since there are |V| vertices.

Steps 3 to 5 take O(max(|V|, |E|)) = O(|V| + |E|) time. The reason is that we have to scan through |V| elements in array Adj, even if all of them point to NULL. On the other hand, the sum of the lengths of all adjacency lists is |E|. We examined each element in adjacency lists once.

Therefore, O(|E| + |V|) + O(|V|) = O(|E| + |V|)

Algorithm for in-degree:

1     For each u in V do

2           in-deg[u] = 0

3     For each u in V do

4           For each v in Adj[u] do

5                 in-deg[v] = in-deg[v] + 1 // count # of edges to v

Steps 1 and 2 take O(|V|).  Steps 3 to 5 take O(max(|V|, |E|)) = O(|V| + |E|) time, since we have to scan all the adjacency lists (even if they may be all empty), and there are |V| lists. Moreover, the sum of the lengths of all adjacency lists is O(|E|). Each element in adjacency lists swill be examined once.

Therefore,  O(|E| + |V|) + O(|V|) = O(|E| + |V|)

Exercise 22.1-2

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

Appling the property of binary tree let sketch the vertices: Base on the assumption this is a directed graph        The equivalent adjacency-matrix representation is as follow:

 1 2 3 4 5 6 7 1 0 1 1 0 0 0 0 2 0 0 0 1 1 0 0 3 0 0 0 0 0 1 1 4 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0

Exercise 22.1-3:

The transpose of a directed graph G  = (V, E) is the graph GT = (V, ET), where ET = {(v,u) Î V x V : (u, v) Î E}. Thus GT = G with all its edges reversed. Describe efficient algorithms for computing GT from G for both adjacency-list and adjacency-matrix representations of G. Analyze the running time of your algorithms.

Figure (A) (figure 22.2 in the textbook) as a directed graph G = (V, E).

Redrawn the graph in reversed order we have figure (B) – adjacency-list and figure (C)  - adjacency-matrix.

{

for each v in V

}

The running time is O = (|V| + |E|).

{

for i = 1 to V.Size

for j = 1 to V.Size

}

The running time is O = |V|2 References:

http://www.comp.nus.edu.sg/~stevenha/programming/prog_graph7.html

http://cody.ebberson.com/classes/csce423/hwk2/

Exercise 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.