Questions 1 -3:
Undirected graph
G = (V, E) [Nodes, Edges]
V = "0", "1", "2", "3" , "4", "5", "6", "7"
E = { "0" : {"4", "6", "1"},
"1" : {"0", "2", "6"},
"2" : {"1", "3", "6"},
"3" : {"2", "6"},
"4" : {"0", "5"},
"5" : {"4"},
"6" : {"0", "1", "2", "3"},
"7" : {""}
}
| Node | Set |
|---|---|
| 0 | 1, 4, 6 |
| 1 | 0, 2, 6 |
| 2 | 1, 3, 6 |
| 3 | 2, 6 |
| 4 | 0, 5 |
| 5 | 4 |
| 6 | 0, 1, 2, 3 |
| 7 |
Q.1 - What is the degree of node 7? Enter your answer below as a single integer. For example, if the answer is 25, just enter 25 in the box, and nothing else.
| Node | Set | Degree |
|---|---|---|
| 0 | 1, 4, 6 | 3 |
| 1 | 0, 2, 6 | 3 |
| 2 | 1, 3, 6 | 3 |
| 3 | 2, 6 | 2 |
| 4 | 0, 5 | 2 |
| 5 | 4 | 1 |
| 6 | 0, 1, 2, 3 | 4 |
| 7 | 0 |
A: 0
Q.2 - If A is the adjacency matrix representation for the undirected graph in Question 1, what is the value of A[2,6]? Enter your answer below as a single integer.
| Node | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 6 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
A: 1
Q3. Which one of the following is a (Python) dictionary representation of the degree distribution of the graph in Question 1?
Remember that the sum of the values in the dictionary should be normalized to sum to one.
A: {0: 0.125, 1: 0.125, 2: 0.25, 3: 0.375, 4: 0.125}
Questions 4-6:
Directed graph
G = (V, E) [Nodes, Edges]
V = "0", "1", "2", "3" , "4", "5", "6", "7"
E = { "0" : ([0,4], [0,5], [0,1]),
"1" : ([1,2], [1,6]),
"2" : ([2,3], [2,7]),
"3" : ([3,0], [3,7]),
"4" : ([4,1]),
"5" : ([5,2]),
"6" : (),
"7" : ([7,4], [7,3])
}
| Node | Set |
|---|---|
| 0 | [0,4], [0,5], [0,1] |
| 1 | [1,2], [1,6] |
| 2 | [2,3], [2,7] |
| 3 | [3,0], [3,7] |
| 4 | [4,1] |
| 5 | [5,2] |
| 6 | [] |
| 7 | [7,4], [7,3] |
Q4. How many nodes in the graph have in-degree 2? Enter your answer below as a single integer.
| Node | Set | Degree Out | Degree In |
|---|---|---|---|
| 0 | [0,4], [0,5], [0,1] | 3 | 1 |
| 1 | [1,2], [1,6] | 2 | 2 |
| 2 | [2,3], [2,7] | 2 | 2 |
| 3 | [3,0], [3,7] | 2 | 2 |
| 4 | [4,1] | 1 | 2 |
| 5 | [5,2] | 1 | 1 |
| 6 | [] | 0 | 1 |
| 7 | [7,4], [7,3] | 2 | 2 |
A: 5
Q5. If A is the adjacency matrix of the graph in Question 4, what is the value of entry A[2,1]? Enter your answer below as a single integer.
A: 0
Q6. How many nodes in the graph of Question 4 have out-degree 2? Enter your answer below as a single integer. A: 4
Q7. Consider an undirected graph g=(V,E) where |V|=n. What is the maximum possible degree of a node in g?
Enter your answer below as a math expression in nn. To format your expression correctly, please consult this page. Remember to use the Preview button (as well as the Help link) to make sure that your expression is formatted correctly
A: n-1
Q8. Consider an undirected graph g=(V,E) where |V|=n. What is the maximum possible number of edges in g? That is, what is the largest size that E can be?
Enter your answer below as a math expression in n. Remember to use the Preview button (as well as the Help link) to make sure that your expression is formatted correctly.
A: n*(n-1)/2
Q9. In an undirected graph g=(V,E) with n nodes, in how many ways can we connect a specific node u to other nodes in g so that u has degree k (where 0 ≤ k < n)?
A: {n-1 \ k}
For Questions 10-16, we will be referring to the following algorithm for generating random undirected graphs:
Algorithm 1: ER.
Input: Number of nodes n; probability p.
Output: A graph g = (V, E) where g E G(n, p).
1. V <- {0,1...n— 1}
2. E <- 0;
3. foreach {i,j} C V, where i =/= j do
4. a <- random(0, 1); // a is a random real number in [0,1)
5. if a < p then
6. E <- E U {{i,j}};
7. return g = (V, E);
Q10. Suppose that the graph g was produced by running Algorithm ER(n, p). What are lower and upper bounds on the degrees for nodes in g?
A: Lower = 0 and upper = n-1
Q11. How many edges are there in a graph g that is obtained by running Algorithm ER(10, 0)? Enter your answer below as a single integer.
A: 0
Q12. How many edges are there in a graph g that is obtained by running Algorithm ER(10,1)? Enter your answer below as a single integer.
A: 45
Q13. What is the expected value of the degree of a node in a graph gg that is obtained by running ER(n,p)?
Review the notes on basic probability and expected value if necessary.
A: (n−1)p
Q14. What is the probability that a particular node in a graph gg produced by running ER(n, p) has degree k where 0 ≤ k < n?
Hint: The ER procedure can be viewed as conducting a trial on each possible edge in the graph. Each trial has one of two outcomes: generate an edge or don't generate an edge. The probabilities associated with these outcomes are pp and 1-p.
To determine the appropriate formula, we suggest that you review the Wikipedia Page.
A: ( n−1 / k) p^k(1−p)^n−1−k
Q15. Consider a graph gg that is obtained by running ER(n, p). If g is represented by its adjacency matrix, which of the following expressions in n and p grows at the same rate as the running time of ER(n, p)?
A: n^2
Q16. Consider a graph g that is obtained by running ER(n,p) where p=0. If g is represented by its adjacency matrix, which of the following expressions in n and p grows at the same rate as the running time of ER(n,p)
A: n^2
Q17. Let g be an undirected graph that has nn nodes and mm edges. If g is given by its adjacency matrix, which of the following expressions grows at the same rate as the time that it takes to compute the degree distribution of g?
A: n^2
Q18. Let g be an undirected graph that has n nodes and m edges. If g is given by its adjacency list, which of the following expressions grows at the same rate as the time that it takes to compute the degree distribution of g?
For this problem, you should assume that it takes time proportional to the length of a list to compute its length.
A: m+n