Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

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

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

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
  • Проголосовать: не нравится

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