3. Consider an adjacency matrix representation of G = (V, E) Assume vertices are numbered 1, 2, … |V|

The representation consists of a matrix AVxV

              aij =   1    if there is an edge from vertex i to vertex j; 
               0   Otherwise
               
Given nodes u and v, what is the time to determine if there is an edge (u, v) in E.

 O( 1 )
 O(|V|^2)
 O(|V|*|E|)
 O(|V|+|E|)

I selected the 3rd option but it is incorrect. Can someone briefly explain this question?

4. Consider an adjacency list representation of an undirected graph G = (V, E). where V is the set of vertices and E is the set of edges.
Each node has a list of the edges that include it as an endpoint. What is the total length of all those lists of edges?

 |E|
 2|E|
 2|V|
 2|V^2|
 
 The answer is 2|E|, but why? Is this because 2 vertices are required to create an edge?
 
 6. Consider an adjacency matrix representation of G = (V, E) Assume vertices are numbered 1, 2, … |V|
The representation consists of a matrix AVxV

              aij =   1    if there is an edge from vertex i to vertex j; 
               0   Otherwise
               
How much time does it take to list all vertices adjacent to a vertex u?

 O(|V|^2) 
 O(|V|)
 O(|V|+|E|) 
 O(|V|*|E|)
 
 I know the answer for this exercise is the last option, but why? Why does the number of vertices/edges determine the time?

yxu22 wrote:

3. Answer is O(1)

In an adjacency matrix, for example,

          A       B        C

A        0        1         1

B        1        0         0

C        1        0         0

for example, the underscore 1 means there exists an edge between vertex A and vertex B.

So if we want to determine if there is an edge (u,v) in E. We only need to check the element of matrix in u th row, v th column.

It takes constant time. We only check something like return ( Matrix(u,v) == 1 ) 

 

4. Because it is an undirected graph. Each edge would be listed twice in an adjacency list.

For example, there is an edge between vertex A and vertex B.

In A's list, we would have a B

In B's list, we would have a A

They are the same edge. We store it twice.

So O( 2|E| )

 

6. Answer is O( |V| )

According to the example above

          A       B        C

A        0        1         1

B        1        0         0

C        1        0         0

For example, if we need to list all vertices adjacent to vertex A, we need to check all columns( or rows) of A.

Then it takes O( |V| ) time.

I understood the rest. However, can you give me an example of an adjacency list of a given graph?

Adjacency List (or Array) representation of graphs

array (or list) of vertices
array (or list) of edges
each edge points to its endpoints
each vertex points to edges incident on it

I know those are the properties.

yxu22 wrote:

          A       B        C

A        0        1         1

B        1        0         0

C        1        0         0

Convert this adjacency matrix to adjacency list:

List of vertices { A, B, C }

List of A { B,C }

List of B { A }

List of C { A }

It's all clear to me now, thanks!