Filtr seznamu úloh?
Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.
Škály
Obtížnost
Štítky
Typ úlohy
«
«
k-regulární bipartitní graf
Úloha číslo: 3769
Dokažte, že hrany k-regulárního bipartitního grafu lze vyjádřit jako sjednocení k perfektních párování.
Nápověda
Dokazujte indukcí a použijte Hallovu větu.
Řešení
Jsou-li A,B části bipartitního grafu, potom pro každou I⊆A platí, že z I vychází právě k|I| hran. Pokud by Y=N(I) obsahovalo méně než |I| vrcholů, vedlo by do Y méně než k|I| hran, což nelze.
Hallova podmínka je splněna a proto v grafu existuje perfektní párování P, tedy takové, které obsahuje všechny vrcholy grafu. Odebráním hran tohoto párování dostaneme (k−1)-regulární bipartitní graf.
Jsou-li dle indukce hrany tohoto zmenšeného grafu rozložitelné na perfektní párování, přidáním P do rozkladu získáme rozklad původního grafu.
