***367 convention = increasing order*** 1. Consider the following directed graph
ID: 3692599 • Letter: #
Question
***367 convention = increasing order***
1.
Consider the following directed graph, which is given in adjacency list form and where vertexes have numerical labels:
The first line indicates that the graph contains a directed edge from vertex 1 to vertex 2, from 1 to vertex 4, and 1 to 6, and likewise for subsequent lines.
A. List the nodes that have a degree of 3.
B. List the nodes in the order they're visited by depth-first search starting at vertex 3. When choosing successors, use the 367 convention of increasing numerical order.
C. Show the corresponding breadth-first search spanning tree for the graph above starting at vertex 8. When choosing successors, use the 367 convention of increasing numerical order. Draw your tree either graphically or in the same manner using characters as done in prior assignments. Verify that your trees in the pdf file looks okay before submitting.
2.
Consider the following directed graph, which is given in adjacency list form as described above and where vertexes have numerical labels:
Show the topological ordering for the graph above using the iterative method covered in lecture (rather than the recursive method in the readings). Use the 367 convention of choosing vertexes in increasing numerical order.
3.
Consider the following undirected graph, which is given in adjacency matrix form and where vertexes have character labels and edges have non-negative integer weights (no value indicates no edge exists):
A. List the node(s) that have a degree of 4.
B. Trace Dijkstra's algorithm starting at node E by completing the table started below where each row represents one iteration of the algorithm.
C. What is the shortest path from E to A? Give a list of vertexes starting at E and ending at A.
D. What is the shortest path from E to G? Give a list of vertexes starting at E and ending at G.
Iteration List of Visited Vertexes and theirshortest distances from start Priority Queue's items
(listed in increasing order) 0 - 0 E 1 E 0 1 F, 3 D, 7 B 2 E 0, F 1
Explanation / Answer
Answer to 1-
A. Degree: the number of edges connected to the node.
The nodes with Degree 3 are 1, 6, 8.
To answer B & C please mention in clear about the statement "use the 367 convention of increasing numerical order"
Answer to 2-
Topological Ordering
In a directed acyclic graph (DAG), the nodes can be ordered such that each node in the ordering comes before all the other nodes to which it has outbound edges. This is called a topological sort of the graph. In general, there is not a unique topological order for a given DAG. If there are cycles in the graph, there is no topological ordering. Topological orderings have many uses for problems ranging from job scheduling to determining the order in which to compute quantities that depend on one another.
To answer this question what methods that are covered in the lecture were not mentioned under which the approach to the answer is needed.
Answer to 3-
A. The nodes with Degree 4 are A, C, D.
and to answer the B,C,D the graph representation is not properly mentioned i.e it is not in proper format.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.