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?
1 answer
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.
VladD VladD
183k 16 gold signs 228 silver marks 434 bronze marks
|