Brain Dump

Matching

Tags
math

Is a sub-graph of a bipartite graph such that none of the chosen edges have a common vertex.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node (l1) [draw, circle] {};              \node (r1) [draw, circle, right=of l1] {};
    \node (l2) [draw, circle, below=of l1] {}; \node (r2) [draw, circle, below=of r1, right=of l2] {};
    \node (l3) [draw, circle, below=of l2] {}; \node (r3) [draw, circle, below=of r2, right=of l3] {};
    \node (l4) [draw, circle, below=of l3] {}; \node (r4) [draw, circle, below=of r3, right=of l4] {};
    \node (l5) [draw, circle, below=of l4] {}; \node (r5) [draw, circle, below=of r4, right=of l5] {};

    \draw [color=red]
	  (l1) -- (r1)
	  (l2) -- (r3)
	  (l4) -- (r5);
    \draw [color=black!30!white]
	  (l1) -- (r2)
	  (l2) -- (r2)
	  (l3) -- (r3)
	  (l3) -- (r4)
	  (l3) -- (r5)
	  (l4) -- (r4)
	  (l5) -- (r5);
  \end{tikzpicture}
  \caption{An example matching with the red lines showing the edges included in the
matching and the grey-lines showing the edges excluded from the matching but still
visible in the base graph \( G \).}
\end{figure}

Matching Improvement example

We define an Alternating Path as a path starting from an unmatched vertex in the left hand side of a bipartite-graph to an unmatched vertex on the right hand side such that the edges in the path are alternatingly in and out of the original matching.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node (l1) [draw, circle] {\( x_1 \)};              \node (r1) [draw, circle, fill=black, text=white, right=of l1] {\( y_1 \)};
    \node (l2) [draw, circle, below=of l1] {\( x_2 \)}; \node (r2) [draw, circle, fill=black, text=white, below=of r1, right=of l2] {\( y_2 \)};
    \node (l3) [draw, circle, below=of l2] {\( x_3 \)}; \node (r3) [draw, circle, fill=black, text=white, below=of r2, right=of l3] {\( y_3 \)};

    \draw [color=red]
	  (l2) -- (r1)
	  (l3) -- (r2);
    \draw [color=black!30!white]
	  (l1) -- (r1)
	  (l1) -- (r2)
	  (l2) -- (r2)
	  (l2) -- (r3)
	  (l3) -- (r3);
  \end{tikzpicture}
  \caption{An example matching.}
  \label{fig:match-improv-eg}
\end{figure}

For example the matching shown in fig:match-improv-eg has an alternating path of \[ x_1 - y_1 \bm{=} x_2 - y_2 \bm{=} x_3 - y_3 \] Where \( - \) represents a path not-in the matching and \( \bm{=} \) represents one in the path.

\begin{figure}
  \centering
  \begin{tikzpicture}
    \node (l1) [draw, circle] {\( x_1 \)};              \node (r1) [draw, circle, fill=black, text=white, right=of l1] {\( y_1 \)};
    \node (l2) [draw, circle, below=of l1] {\( x_2 \)}; \node (r2) [draw, circle, fill=black, text=white, below=of r1, right=of l2] {\( y_2 \)};
    \node (l3) [draw, circle, below=of l2] {\( x_3 \)}; \node (r3) [draw, circle, fill=black, text=white, below=of r2, right=of l3] {\( y_3 \)};

    \draw [color=red]
	  (l1) -- (r1)
	  (l2) -- (r2)
	  (l3) -- (r3);
    \draw [color=black!30!white]
	  (l1) -- (r2)
	  (l2) -- (r1)
	  (l2) -- (r3)
	  (l3) -- (r2);
  \end{tikzpicture}
  \caption{An improved version of the matching from \autoref{fig:match-improv-eg}.}
  \label{fig:match-improv-eg-final}
\end{figure}

Given an alternating path we can simply toggle the status of the edges in and not-in the matching to get a new matching covering both the vertices in the existing matching and covering a new edge, giving us a more complete matching. In this case that would be \[ x_1 \bm{=} y_1 - x_2 \bm{=} y_2 - x_3 \bm{=} y_3 \] You can see this improved matching in fig:match-improv-eg-final.

Note: if you're unable to find an alternating-path you can conclude the current matching is maximal and it cannot be improved.

Links to this note