Блог пользователя parveen1981

Автор parveen1981, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +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.