Heiratssatz

Einfache Sprache

Def. Heiratssatz

Sei $G=(V,E)$ ein Bipartiter Graph mit der Bipartition $V=A\dot\cup B$ mit $A,B\subseteq V$. Dann hat $G$ ein matching der Größe |A| g.d.w. $|N(S)|\leq |S|$ für jedes $S\subseteq A$ gilt, wobei $N(S) = \{b\in B\mid \exists a\in S: \{a, b\}\in E\}$.