Input: number of edges and vertices, and array of all edges in graph.Output: array of edges that construct a matching, so that:$$\frac{\text{the number of edges in this matching}}{\text{the number of edges in maximum matching}} \geq \frac{1}{2}$$Algorithm I implemented Loop:take a random edge (actually in order it was given);if we can add it to our matching then add;Finally we get a matching. The proof of condition from given section by contradiction: let's compare our matching with the maximum one. Let's consider one edge from our matching. There're two cases: the same edge is in the maximum matching or not. If it belongs to the maximum then it's OK. If not, then there's could be not more than two adjacent edges in maximum matching. Let's assume that it happened with each edge in our matching. Nevertheless, our matching satisfies the given conditions: it has not less than 0.5 of number of edges in maximum matching.However the proof seems not really good to me. I guess there also should be a proof by induction by edges of matching. But I can't come up with a good idea.
Correctness proof: 2-approximation of greedy matching-algorithm
algorithm analysis;approximation;correctness proof;matching
Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching). For all $e\in M'$ let $M_e\subseteq M$ be the set of edges in $M$ who have common vertices with $e$, meaning all $e_M\in M$ such that $e_M\cap e\neq\emptyset$. Obviously $\forall e\in M': |M_e|\le 2$, since at the worst, $e=(u,v)$ and both $u,v$ are matched to some other vertex in $M$.Note that $M=\bigcup\limits_{e\in M'}M_e$. To see why, suppose for the purpose of contradiction that there exists $e\in M$ with no common vertices with any $e'\in M'$. This means that our algorithm could have added $e$ to $M'$, contradiction. So we have:$|M|\le\sum\limits_{e\in M'}|M_e|\le 2|M'|$.