You are Here: Home >< Maths

# Bipartite matching question watch

1. So an alternating path is one that includes an arc already in the graph, then one that is not but possible then repeats etc....
I hope you understand what i mean, when the textbook first explained it to me it sounded really wierd :P
2. (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....
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!
3. 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

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: November 7, 2016
The home of Results and Clearing

### 2,978

people online now

### 1,567,000

students helped last year
Today on TSR

### University open days

1. Sheffield Hallam University
Tue, 21 Aug '18
2. Bournemouth University
Wed, 22 Aug '18
3. University of Buckingham
Thu, 23 Aug '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams