A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm (Q1323480)

A matching algorithm is developed. Graph searching procedures are proposed; the synchronization of events plays a role very important in the conception. In Subsection 2.1 the bipartite case is studied, and the nonbipartite case is analyzed in 2.2. Two figures give the ideas related with the proposed linear time algorithm. Two theorems fix properties of the \(\text{minlevel}(v)\) and \(\text{maxlevel}(v)\) paths attainable. \(\text{Minlevel}(v)\) is not breadth first search (BFS). The notion of \[ \text{tenacity}(v)=\text{evenlevel}(v)+ \text{oddlevel}(v) \] is used as an alternative to BFS. Theorems 1 and 2 fix conditions under which \(u\) occurs at \(\text{minlevel}(u)\) distance on another minlevel. The base of a vertex is defined in terms of tenacity. The main result is that the existence of a vertex of finite tenacity ensures the uniqueness of its base. The notion of base permits to introduce blossom as the set \[ \bigl\{v\in V: \text{tenacity}(v)\leq t\text{ and }\text{base}_{>t}(v)= b\bigr\}. \] A theorem establishes that the shortest alternating paths from \(\text{base}(v)\) to \(v\) are tied in a blossom. The nesting of blossoms and some relations between it and an even (odd) level are derived. A theorem establishes a connection among evenlevels, oddlevels of the end points of a bridge and tenacity. Two procedures are developed. The efficiency of one of them is characterized in terms of a set of edges. A theorem establishes the correctness of the algorithms.