Bipartite matching question
So an alternating path is one that includes an arc already in the graph, then one that is not but possible then repeats etc....
However can you start with one that's not possible then one that's already in it.
I hope you understand what i mean, when the textbook first explained it to me it sounded really wierd :P
However can you start with one that's not possible then one that's already in it.
I hope you understand what i mean, when the textbook first explained it to me it sounded really wierd :P
Original post by Toasticide
So an alternating path is one that includes an arc already in the graph, then one that is not but possible then repeats etc....
However can you start with one that's not possible then one that's already in it.
I hope you understand what i mean, when the textbook first explained it to me it sounded really wierd :P
However can you start with one that's not possible then one that's already in it.
I hope you understand what i mean, when the textbook first explained it to me it sounded really wierd :P
To clarify: An alternating path begins from the initial matching by selecting an unmatched node in one of the sets of the initial matching and connecting it to a node in the other set. Then it matches the node eit just unmatched and so on and so on.
When you say not possible. If a complete matching cannot be made. Alternating paths will just take you to the optimal matching (assuming you are wise with it!) and continued applications of the algorithm lead to repeats.
In terms of a complete matching not being possible then it is not possible to get a complete matching - such a silly statement by me!
Yeah i just realised i could've made the question much simpler by asking do you have to start with one already-in then one not-in or can you vice versa.
Thanks, i understand
Thanks, i understand
Quick Reply
Related discussions
- Oxford PPL vs Cambridge PBS?
- Oxford PPL vs Cambridge PBS?
- dropping A-level economics
- IBM Matching Pool 2024/25
- NEA
- Need help with this AL Maths Q
- IBM placement year 2023
- Only answer if you’ve done an a level that matches this?
- carbonyls a level chemistry
- GCSE Computer Science QUESTION
- Can anyone help me on this Physics IGCSE Question?
- Account details don’t match with parents STUDENT FINANCE ENGLAND!
- Anyone with experience as an Insolvency Paralegal (EO) with the Civil Service?
- Hard integration Q
- Supporting a Student Finance application
- How many clothes should you have for sixth form?
- Binomial expansion with negative power
- IBM degree apprenticeship 2023
- Here’s an app to find YOUR perfect housemates!!
- AS maths factorization help
Latest
Trending
Last reply 4 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
Trending
Last reply 4 days ago
Did Cambridge maths students find maths and further maths a level very easy?Last reply 2 weeks ago
Edexcel A Level Mathematics Paper 2 unofficial mark scheme correct me if wrongMaths
71
