McqMate

Q. |
## Which of the following is false? |

A. | the spanning trees do not have any cycles |

B. | mst have n – 1 edges if the graph has n edges |

C. | edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph |

D. | removing one edge from the spanning tree will not make the graph disconnected |

Answer» D. removing one edge from the spanning tree will not make the graph disconnected | |

Explanation: every spanning tree has n – 1 edges if the graph has n edges and has no cycles. the mst follows the cut property, edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph. |

1.1k

0

Do you find this helpful?

3

View all MCQs in

Design and Analysis of AlgorithmsNo comments yet

- Which of the following is false in the case of a spanning tree of a graph G?
- Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
- Which of the following is false about the Kruskal’s algorithm?
- Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
- Which of the following strategies does the following diagram depict?
- Which of the following strategies does the following diagram depict?
- You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem?
- Recursion is similar to which of the following?
- Which of the following problems can’t be solved using recursion?
- In general, which of the following methods isn’t used to find the factorial of a number?