Orientace řídkého grafu
Úloha číslo: 3773
Mějme graf \(G=(V,E)\) takový, že pro nějaké \(k\in\mathbb N\) platí: \(\forall H \subseteq G: |E(H)| \leq k \cdot |V(G)|\). Ukažte, že existuje orientace \(G\) taková, že \(\forall u \in V: \deg_{in} (u) \leq k\).
Nápověda
Vhodně upravte graf incidence.
Řešení
Vytvoříme množinový systém, kde množiny jsou indexovány hranami. Pro každou hranu \(e=(u,v)\) vytvoříme množinu od \(2k\) prvcích \(M_e=\{u_1,…,u_k,v_1,…,v_k\}\), neboli každý vrchol nahradíme jeho \(k\) kopiemi.
V tomto množinovém systému je splněna Hallova podmínka, proto každou hranu \(e\) lze reprezentovat některou z \(k\) kopií \(u_i\) vrcholu \(u\). V tomto případě budeme směřovat hranu \(e\) do \(u\). Vzhledem k tomu, že od \(u\) bylo vytvořeno \(k\) kopií, mohou jeho kopie reprezentovat nejvýše \(k\) hran a proto je \(\deg_{in} (u) \leq k\)
