Problem D: For each of the following parts, state True or False. If true, give a...

 

Transcribed Image Text:

Problem D: For each of the following parts, state True or False. If true, give a short proof. If false, giver a counterexample: (1). Using Kruskal's algorithm, edges are (always) inserted into the MST in the same order as using Prim's algorithm. (2). If an edge e is part of a Shortest Path Tree rooted at A then it must also be part of a Shortest Path Tree rooted at B. (3). If all edge costs are increased by 2 the Shortest Path Tree rooted at A remains the same tree. (4). If all edge costs of all edges touching node A are increased by 2, the shortest path tree rooted at A remains the same. (5). If all edge costs of all edges touching node A are increased by 2, the minimum spanning tree rooted at A remains the same. 10 H 10 5 B A 6 1 7 G 11 4 3 F C 8 2 D 9 Problem D: For each of the following parts, state True or False. If true, give a short proof. If false, giver a counterexample: (1). Using Kruskal's algorithm, edges are (always) inserted into the MST in the same order as using Prim's algorithm. (2). If an edge e is part of a Shortest Path Tree rooted at A then it must also be part of a Shortest Path Tree rooted at B. (3). If all edge costs are increased by 2 the Shortest Path Tree rooted at A remains the same tree. (4). If all edge costs of all edges touching node A are increased by 2, the shortest path tree rooted at A remains the same. (5). If all edge costs of all edges touching node A are increased by 2, the minimum spanning tree rooted at A remains the same. 10 H 10 5 B A 6 1 7 G 11 4 3 F C 8 2 D 9