Tutte-Berge Formel
Einfache Sprache
Die Tutte-Berge Formel erlaubt die Größe der matchings nach oben hin abzuschätzen.
Def. Tutte-Berge Formel
Gegeben ein Graph $G = (V,E)$. Sei $o(\cdot)$ die Anzahl an der untereinander zusammenhängenden Teilgraphen mit ungerader Größe eines Graphen. Dann gilt
$$\max_{match.\;M}|M| = \min_{U\subseteq V}\frac{1}{2}\left(|V|+ |U| - o(G\setminus U)\right)$$
Beweis:
Gegeben ein genereller (also auch nicht bipartiter) Graph $G=(V,E)$. Ziel ist es eine obere Schranke für die Größe eines matchings auf $G$ zu bekommen.
Sei $U\subseteq V$. Wenn wir $U$ und alle Kanten die zu einem Knoten in $U$ inzident sind, dann werden höchstens $|U|$ Kanten eines matching entfernt. Wir definieren $G$ ohne $U$ wie folgt
$$G\setminus U:= \left(V\setminus U,\{e\in E:|e\cap U|=0\}\right)\;.$$Wir nehmen an, dass $G\setminus U$ aus genau $k$ zusammenhängenden Teilgraphen, mit Knotenmengen $C_1,\ldots,C_k\subseteq V$ so, dass die Disjunkte Vereinigung der Teilgraphen $V\setminus U$ ergibt. Also $V\setminus U = \dot\bigcup_{i\in[k]}C_i\;.$ Dann kann die Größe des restlichen matchings durch $\sum_{i\in[k]}\lfloor\frac{1}{2}|C_i|\rfloor$ nach oben beschränkt werden. Es ergibt sich
$$|M| \leq |U| + \sum_{i\in[k]}\left\lfloor\frac{|C_i|}{2}\right\rfloor\;.$$Sei $o(\cdot)$ die Anzahl an der untereinander zusammenhängenden Teilgraphen mit ungerader Größe eines Graphen. Dann ergibt sich folgende Gleichung
$$\begin{align}|M| &\leq |U| + \sum_{i\in[k]}\left\lfloor\frac{|C_i|}{2}\right\rfloor &\Huge|\normalsize\text{siehe oben}\\&= |U| + \sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ even}\end{array}}\left\lfloor\frac{|C_i|}{2}\right\rfloor +\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}\left\lfloor\frac{|C_i|}{2}\right\rfloor &\Huge|\normalsize\begin{array}{c}\text{Fallunterscheidung}\\\text{nach grade/ungrade}\end{array}\\&= |U| + \sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ even}\end{array}}\frac{|C_i|}{2} +\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}\frac{|C_i|-1}{2}&\Huge|\normalsize\text{Abrunden überflüssig}\\&= |U| + \frac{1}{2}\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ even}\end{array}}|C_i| +\frac{1}{2}\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}(|C_i|-1)&\Huge|\normalsize\text{Eig. Vereinigung}\\&= |U| + \frac{1}{2}\left(\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ even}\end{array}}|C_i| +\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}(|C_i|-1)\right)&\Huge|\normalsize\text{Ausklammern}\\&= |U| + \frac{1}{2}\left(\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ even}\end{array}}|C_i| +\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}|C_i|-\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}1\right)&\Huge|\normalsize\text{Eig. Summe}\\&= |U| + \frac{1}{2}\left(\sum_{ i\in[k] }|C_i|-\sum_{\begin{array}{c} i\in[k]\\|C_i| \text{ odd}\end{array}}1\right)&\Huge|\normalsize\text{Eig. Summe}\\&= |U| + \frac{1}{2}\left(\sum_{ i\in[k] }|C_i|-o(G\setminus U)\right)&\Huge|\normalsize\text{Def. $o$}\\&= |U| + \frac{1}{2}\left(|V|- |U| -o(G\setminus U)\right)&\Huge|\normalsize\text{Def. $C_i$}\\&= \frac{2}{2}|U| + \frac{1}{2}\left(|V|- |U| -o(G\setminus U)\right)&\Huge|\normalsize\text{Erweitern}\\&= \frac{1}{2}\left(2|U| + |V|- |U| -o(G\setminus U)\right)&\Huge|\normalsize\text{Ausklammern}\\&= \frac{1}{2}\left(|V|+ |U| -o(G\setminus U)\right)&\Huge|\normalsize\text{Vereinfachen}\\\end{align}$$Wir haben also
$$|M| \leq \frac{1}{2}\left(|V|+ |U| -o(G\setminus U)\right)$$Daraus ergibt sich, dass die maximale Größe eines matchings gleich des $U$ für das der rechte Teil minimiert wird.