Question

For each node in an undirected graph, let twodegree$\left[\mathbf{u}\right]$be the sum of the degrees of’s neighbors. Show how to compute the entire array of two degree$\left[.\right]$ values in linear time, given a graph in adjacency list format

Short answer

The twodegree[u] be the sum of the degrees of u’s neighbors in linear time is$\mathrm{twodegree}\left[\mathrm{u}\right]=\mathrm{twodegree}\left[\mathrm{u}\right]+\mathrm{degree}\left[\mathrm{w}\right]$ and this statement is proved.

Step-by-step solution

Step 1: Adjacency List

The representation of the list contain an array known as an adjacency list.

An adjacency list consists of a linked list for each vertex.

The size of the array is the same as the number of vertices in it.

If the graph is an undirected graph, then each edge appears twice in the list.

Each list consists of the name of the vertex.

Step 2: Twodegree[u] be the sum of the degrees of ’s neighbors

Consider undirected graph G. For each node u in G, let two degree[u] be the sum of the degrees of u's neighbor nodes. The degree of a node in an undirected graph is the number of edges connected to the node.

For each node in a graph there is a list. It will take a linear time in adjacency list and it always assign a degree value to each node. And while iterating from the list than the total number of the vertex is the degree of the vertex.

It takes linear time to go through the adjacency list and assign each node a degree value. Then have to perform another linear time algorithm to sum the totals, either by traversing the list a second tome or using a depth first search which gives O(2n). Then iterate the list, the total number of vertices in the list is the degree of the vertex, store these values in an array. Then assigned a degree for each vertex, go through the list again and sum the degrees of its list. It performed by taking these steps as follows, firstly the degree of u is zero where u is a vertex and w is edge and degree of u is defined as a sum of degree of itself plus one after that the two degree is equals to the sum of the degree of w and two degree of u.

$$\begin{gathered} \mathrm{for}\mathrm{all}\mathrm{u}\in \mathrm{V}: \\ \mathrm{degee}\left[\mathrm{u}\right]=0 \\ \mathrm{for}\mathrm{all}(\mathrm{u};\mathrm{w})\in \mathrm{E}: \\ \mathrm{degree}\left[\mathrm{u}\right]=\mathrm{degree}\left[\mathrm{u}\right]+1 \end{gathered}$$

$$\begin{gathered} \mathrm{for}\mathrm{all}\mathrm{u}\in \mathrm{V}: \\ \mathrm{twodegee}\left[\mathrm{u}\right]=0 \\ \mathrm{for}\mathrm{all}(\mathrm{u};\mathrm{w})\in \mathrm{E}: \\ \mathrm{twodegree}\left[\mathrm{u}\right]=\mathrm{twodegree}\left[\mathrm{u}\right]+\mathrm{degree}\left[\mathrm{w}\right] \end{gathered}$$

Here, the two degree [u] be the sum of the degrees of u’s neighbors. the array of two-degree values in linear time. Is shown that the two degree of u is the sum of the its nearby vertices.