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.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze