Bipartite Graphen

bipartit & Matching

Ein Graph $G=\left(E,K\right)$ heißt bipartit, falls $E=E_{1}\dot{\cup}E_{2}$ und $K$ nur aus Knoten besteht, die jeweils eine Ecke aus $E_{1}$ mit einer aus $E_{2}$ verbinden.

Eine Teilmenge $K'\subseteq K$ heißt Matching, falls keine zwei Kanten aus $K'$ eine gemeinsame Ecke besitzen. Ein Matching heißt perfekt, falls $\left\vert K'\right\vert=\left\vert E_{1}\right\vert$ oder $\left\vert K'\right\vert=\left\vert E_{2}\right\vert$.

• ein bipartiter Graph $G_{m,n}$ (mit $\left\vert E_{1}\right\vert=n$ und $\left\vert E_{2}\right\vert=m$), heißt vollständig, wenn je zwei Ecken aus verschiedenen Ecken durch eine Kante verbunden sind.
  • für $n,m$ gerade $\Leftrightarrow$ $G_{m,n}$ ist eulersch
  • für $n=m\geq2\Leftrightarrow G_{m,n}$ hamiltonisch
  • GEW-Graph: $n=3\; m=3$
  • für $n,m\geq3$ ist $G_{m,n}$ nicht plättbar

Heiratssatz / Existenz eines perfekten Matching

Sei $G=\left(E_{1}\dot{\cup}E_{2},K\right)$ ein bipartiter Graph. Für jede Teilmenge $U\subseteq E_{1}$ definieren wir $\deg\left(U\right):=$ Anzahl der Ecken aus $E_{2}$, die mit einer Ecke aus $U$ verbunden sind. Dann gilt:

$U$ besitzt ein perfektes Matching, genau dann wenn $\forall U\subseteq E_{1}:\deg\left(U\right)\geq\left\vert U\right\vert$.

• $\deg\left(U\right)\leq\sum_{v\in U}\deg\left(v\right)$
• jeder bipartite $k$-reguläre Graph hat ein perfektes Matching
• Wenn $\left\vert E_{1}\right\vert\neq\left\vert E_{2}\right\vert\Rightarrow$ Kanten weglassen und Teilgraph betrachten