parveen1981's blog

By parveen1981, history, 7 weeks ago,

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
 » 7 weeks ago, # |   +1 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.