Practice Complete Matching (25.1.4.3) - Introduction to Bipartite Graphs and Matching

Practice: Complete Matching

Lesson 25.1.4.3Introduction to Bipartite Graphs and Matching

Practise this section

8 questions

Flashcard drill
2 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
2 questions · about 1 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is a bipartite graph?
Show hintHide hint
Think about how vertices can be categorized.
Question 2.
Define maximum matching in a bipartite graph.
Show hintHide hint
Consider the total number of pairs.
3Question 3.
Which of the following defines a bipartite graph?
- A graph with all vertices connected to each other.
- A graph whose vertices can be divided into two sets.
- A graph without edges.
Show hintHide hint
Think about how vertices are grouped.
4Question 4.
True or False: A maximal matching is always a maximum matching.
- True
- False
Show hintHide hint
Consider the sizes of the matchings.
Question 5.
Design a bipartite graph representing a system where seven students need to be assigned to five projects. Demonstrate if a complete matching is possible based on the skills listed for each student.
Show hintHide hint
Use Hall's theorem to check if the coverage is sufficient.
Question 6.
Given a bipartite graph showing four employees and their skills related to three tasks, demonstrate potential matchings and identify which type of matching it constitutes.
Show hintHide hint
Compare the number of skills to needed tasks.

4 more questions in this section. Enroll free to practise them all.