Satz von Hall

Ein bipartiter Graph $G:=(A\dot{\cup }B,E)$ enthält ein matching von $A$ genau dann, wenn $|N(S)|\ge |S|$ für alle $S\subseteq A$.

Matching von S (Hall-Kontext)

Sei $G=(A\dot{\cup }B,E)$ und $S\subseteq V(G)$.
Ein matching von $S$ ist ein matching $M$ von $G$ mit $S\subseteq V(M)$.

Hall-Bedingung

Offensichtlich muss folgende notwendige Bedingung gelten:

Links

• DS_vollständiger_foliensatz.pdf
• Matching