Answer True or False to each of the questions below. Answer true only if it alwa

Question

Answer True or False to each of the questions below. Answer true only if it always is true as stated, with no additional assumptions. No explanation is needed, but good explanations may get partial credit.

(a) In a connected graph, breadth-first search starting from a node i is an optimal algorithm for finding the minimum-hop path from node i to any other node.

(b) The adjacency matrix for a graphs G(N A) is always a symmetric matrix, i.e the same above and below the diagonal.

(c) One way to do a topological sort on a DAG graph is to first do a DFS and reverse the order.

(d) Consider an undirected acyclic graph, G(N A), with n = jNj nodes and a = jAj arcs. If a =n - 4, G(N;A) is a forest with 3 trees.

(e) If a weighted directed graph G(N A) has a single negative cycle, there is never a shortest path p(1!n) from node 1 to node n.

(f) Consider a minimum spanning tree problem in a connected, weighted graph with positive and negative weights which but no negative weight cycles. Then, both Dijkstras and Bellman-Ford algorithms will give the short distances from node 1 but Dijkstras is in general faster.

(g) Consider an undirected graph , G(N A). The connected component for node i and node j are identical if and only if there is a path from i to j.

(h) In the Bellman-Ford algorithm, the temporary distance label d(i) assigned to node I after k nodes have been scanned has the interpretation of being the shortest distance achievable by any path from the origin to node i with k or less hops.

(i) An undirected graph with no cycles is a tree.

(j) The worst case complexity of the fastest minimum spanning tree algorithm is O(Nlog(N)), where N is the number of nodes in the graph.

(k) Consider an undirected graph where, for every pair of nodes i j, there exists a unique

simple path between them. This graph must be a tree.

(l) Nodes n1 and n2 are neighbors in an undirected graph only if there is a path between

them.

(m) Consider a minimum spanning tree T in a connected undirected graph (N, A). Assume that the arc weights in the graph are all distinct (e.g. no two arcs have the same weight). Then, an arc i, j in T must have the property that it is either the minimum weight arc connected to node i or the minimum weight arc connected to node j.

Explanation / Answer

a) In a connected graph, breadth-first search starting from a node i is an optimal algorithm for finding the minimum-hop path from node i to any other node.FALSE

(b) The adjacency matrix for a graphs G(N A) is always a symmetric matrix, i.e the same above and below the diagonal.TRUE

(c) One way to do a topological sort on a DAG graph is to first do a DFS and reverse the order.TRUE

(d) Consider an undirected acyclic graph, G(N A), with n = jNj nodes and a = jAj arcs. If a =n - 4, G(N;A) is a forest with 3 trees.TRUE

(e) If a weighted directed graph G(N A) has a single negative cycle, there is never a shortest path p(1!n) from node 1 to node n.FALSE

(f) Consider a minimum spanning tree problem in a connected, weighted graph with positive and negative weights which but no negative weight cycles. Then, both Dijkstra

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.