Show the steps of deriving your answers. Points will be deducted for answers without adequate steps discussed or not compliant with the specification. Submit your homework via Blackboard as one PDF or Word document. Refer to the grading guidelines posted on Blackboard to understand how the submitted exercises will be graded.
(25) [Spanning tree] Consider an undirected connected graph G = (V, E) and a connected subgraph G` = (V, E`) of G where E` is a subset of E. Prove or disprove that G` is a spanning tree of G if and only if G` is acyclic.
(25) [Single-source shortest-path: algorithm tracing] (Source: Cormen et al., Introduction to Algorithms (modified)) Show the tracing of Dijkstra’s shortest path search algorithm on the weighted directed graph shown below. Do it twice, first starting with the node s and, second, starting with the node z. Each time the shortest path to a new node is determined, show the resulting shortest path to the node and show inside the node the shortest distance to the node.
Last modified: September 26, 2019
