parveen1981's blog

Need Help: Augmenting Path for Maximum Matching
By parveen1981, history, 4 years ago, In English

I was learning about maximum matching in bipartite graphs but I can't understand one thing i.e. augmenting path always has one extra matching edge.
Link: Hopcroft Karp Algorithm Geeks for Geeks
Can someone please help me with this
Thank you in advance.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Augmenting path has an odd number of edges, let us name them $$$e_0, e_1, e_2, \ldots, e_{2 k}$$$.
The edges selected previously are $$$e_1, e_3, e_5, \ldots, e_{2 k - 1}$$$, there are $$$k$$$ of them.
If we instead select $$$e_0, e_2, e_4, \ldots, e_{2 k}$$$, there are $$$k + 1$$$ of them.

→ Reply