For a directed network in which in- and out-degrees are

Question

1. For an undirected network of n vertices stored in adjacency list format show that:

a) It takes time 0 (n (n + m)) to find the diameter of the network.

b) It takes time O( (k)) on average to list the neighbors of a vertex, where (k) is the average degree in the network, but time O( (k² )) to list the second neighbors.

2. For a directed network in which in- and out-degrees are uncorrelated, show that it takes time 0(/m² / n) to calculate the reciprocity of the network. Why is the restriction to uncorrelated degrees necessary? What could happen if they were correlated?