Many places write that its correctness obviously follows from the theorem of Berge. However, it is not clear why if the increasing chain exists, the algorithm will find it?

  • one
    Doesn't it make it difficult for you to formulate a theorem and an algorithm? Or at least provide a link to the wording. - VladD pm

1 answer 1

If I understand correctly, the idea is this.

Let there really be a magnifying chain. As we iterate through all the starting vertices, we will try to start our iteration from the starting vertex of the increasing chain (which, we assumed, exists). In fact, we iterate over all alternating chains (in terms of the text by reference @ReinRaus ) from this vertex, so when sorting, we must get to that very existing chain.