- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- Which theorem gives the relation between...

Q. |
## Which theorem gives the relation between the minimum vertex cover and maximum matching? |

A. | konig’s theorem |

B. | kirchhoff’s theorem |

C. | kuratowski’s theorem |

D. | kelmans theorem |

Answer» A. konig’s theorem | |

Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. |

View all MCQs in:
Design and Analysis of Algorithms

- Which graph has a size of minimum vertex cover equal to maximum matching?
- In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called?
- Maximum matching is also called as maximum cardinality matching.
- Which type of graph has all the vertex of the first set connected to all the vertex of the second set?
- A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
- Under what case of Master’s theorem will the recurrence relation of merge sort fall?
- Under what case of Master’s theorem will the recurrence relation of stooge sort fall?
- Under what case of Master’s theorem will the recurrence relation of binary search fall?
- Which is the correct technique for finding a maximum matching in a graph?
- Who was the first person to solve the maximum matching problem?

Login to Continue

It will take less than 2 minutes

Report MCQ