1) Consider the graph G below. Which of the following show a correct order of ad
ID: 3693477 • Letter: 1
Question
1) Consider the graph G below. Which of the following show a correct order of adding edges to the MST using Kruskal's algorithm?
(a, b), (c, d), (e, d), (f, a), (c, a)
(c, d), (a, b), (e, d), (a, f), (a, c)
(a, b), (c, d), (c, a), (e, d), (f, a)
(a,b), (c, d), (e, d), (a, f), (a, c), (c, e), (f, b), (b, c), (f, e), (b, e)
(a, b), (c, d), (f, a), (d, e), (a, c)
(a, b), (a, f), (a, c), (c, d), (d, e)
2) We call RELAX(u,v,w) on the graph below. What is the value of v.d after the RELAX call?
9
7
6
3) Write the adjacency-list representation of the graph G below. Upload a file with your solution.
4) Which of the following lists are possible topological sorts of the graph G below?
a, e, f,d, b, c
a, d, b, c, e, f
f, d, a, b, c, e
e, d, b, c, a, f
f, a, e, d, b, c
a, e, d, b, c, f
5) Run the dag shortest-paths algorithm on the graph below, where s is the source vertex. Write the v.d and v. values for each vertex v. Darken the shortest-paths tree. Follow the example done in class in Module11.3.pdf. Upload a file with your solution.
6) Consider the graph G below. Which of the following statements are TRUE?
(s,a) = 2
(s,b) =
(s,e) =
(s,c) = 6
(s,d) =
(d,e) = 2
adjacency-matrix graph representation
we can use a Binary Search Tree to represent G
adjacency-list graph representation
such a graph G cannot be represented
8) Run the Dijkstra's algorithm on the graph below, where s is the source vertex. Draw a table that shows the vertices in the queue at each iteration, together with the v.d, v. values for each vertex v in the queue. Write the order in which vertices are added to the set S. Darken the shortest-paths tree. Follow the example done in class in Module 11.4.pdf. Upload a file with your solution.
(a, b), (c, d), (e, d), (f, a), (c, a)
(c, d), (a, b), (e, d), (a, f), (a, c)
(a, b), (c, d), (c, a), (e, d), (f, a)
(a,b), (c, d), (e, d), (a, f), (a, c), (c, e), (f, b), (b, c), (f, e), (b, e)
(a, b), (c, d), (f, a), (d, e), (a, c)
(a, b), (a, f), (a, c), (c, d), (d, e)
2) We call RELAX(u,v,w) on the graph below. What is the value of v.d after the RELAX call?
9
7
6
3) Write the adjacency-list representation of the graph G below. Upload a file with your solution.
4) Which of the following lists are possible topological sorts of the graph G below?
a, e, f,d, b, c
a, d, b, c, e, f
f, d, a, b, c, e
e, d, b, c, a, f
f, a, e, d, b, c
a, e, d, b, c, f
5) Run the dag shortest-paths algorithm on the graph below, where s is the source vertex. Write the v.d and v. values for each vertex v. Darken the shortest-paths tree. Follow the example done in class in Module11.3.pdf. Upload a file with your solution.
6) Consider the graph G below. Which of the following statements are TRUE?
(s,a) = 2
(s,b) =
(s,e) =
(s,c) = 6
(s,d) =
(d,e) = 2
7) Let G = (V,E) be a directed, weighted graph where for any vertices with u v. Which of the following data structures should be used to represent G?
adjacency-matrix graph representation
we can use a Binary Search Tree to represent G
adjacency-list graph representation
such a graph G cannot be represented
8) Run the Dijkstra's algorithm on the graph below, where s is the source vertex. Draw a table that shows the vertices in the queue at each iteration, together with the v.d, v. values for each vertex v in the queue. Write the order in which vertices are added to the set S. Darken the shortest-paths tree. Follow the example done in class in Module 11.4.pdf. Upload a file with your solution.
Explanation / Answer
Question 2):
Consider the graph diagram, then the value of v.d after the RELAX call is 7.
Question 4):
Topological sorting is a directed acyclic graph.
Consider the given diagram, then the following lists are possible topological sorts of the graph G:
e, d, b, c, a, f
f, a, e, d, b, c
Question6):
Consider the given graph, then the true statements are:
(s,a) = 2
(s,c) = 6
(d,e) = 2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.