Párování v inkluzním grafu
Úloha číslo: 3774
Graf \(G_{n,a,b}\) pro přirozená čísla \(a, b \leq n\), \(a \neq b\) je definován:
\(\displaystyle V(G_{n,a,b}) = \{X : X \subseteq \{1{,}2, …, n\}, |X| \in \{a,b\}\}, \)
\(\displaystyle E(G_{n,a,b}) = \{XY: X \subset Y\}. \)
V závislosti na \(a\), \(b\) a \(n\) určete velikost největšího párování tohoto grafu.
Řešení
Graf \(G_{n,a,b}\) je bipartitní, s částmi \(A\), \(B\), kde vrcholy části \(A\) odpovídají \(a\)-prvkovým podmnožinám a podobně vrcholy části \(B\) odpovídají \(b\)-prvkovým.
Všechny vrcholy části \(A\) mají stejný stupeň a také všechny vrcholy části \(B\). V takových grafech platí, že maximální párování obsahuje všechny vrcholy menší z obou částí, jak ukážeme následovně:
Je-li bez újmy na obecnosti \(|A|\le |B|\), a vrcholy z \(A\) mají stupeň \(d\), potom vrcholy z \(B\) mají stupeň stejný nebo menší. Z libovolné \(I\subseteq A\) vychází \(d|I|\) hran, tedy \(|N(I)|\ge \frac{d|I|}d\), a proto je Hallova podmínka splněna.
Odpověď
Maximální párování grafu \(G_{n,a,b}\) obsahuje \(\min\{\binom{n}{a},\binom{n}{b}\}\) hran.