Matching and Allocation Problems (VCE SSCE General Mathematics): Quizzes
📚Quizzes
Practise the questions
10 questions from this quiz
ShowHide
Practise the questions
10 questions from this quiz
What defines a bipartite graph?
What defines a bipartite graph?
Vertices in 2 groups, edges join groups
In a bipartite graph, which connections are never allowed?
In a bipartite graph, which connections are never allowed?
Vertices within the same group
What is an allocation problem?
What is an allocation problem?
Matching items from one group to another
What is a forced assignment in allocation?
What is a forced assignment in allocation?
A vertex with only one edge connection
What defines a complete bipartite graph?
What defines a complete bipartite graph?
Every vertex connects to all in other
What is Step 1 of the Hungarian algorithm?
What is Step 1 of the Hungarian algorithm?
Subtract smallest row value from row
In Step 2, when do you jump to Step 6?
In Step 2, when do you jump to Step 6?
Lines covering zeros = allocations
What happens in Step 3 column reduction?
What happens in Step 3 column reduction?
Subtract smallest from column w/o zero
In Step 5a, what do you do with smallest uncovered value?
In Step 5a, what do you do with smallest uncovered value?
Add to 2-line cells, subtract uncovered
Which matrix calculates the final minimum cost?
Which matrix calculates the final minimum cost?
The original cost matrix