Matematické Fórum
Archiv diskusního fóra o matematice, 2006–2026
Toto je archiv Matematického Fóra.
Fórum je dostupné jen ke čtení.
Můžete se ale zaregistrovat na náš Discord server.
#1 07. 06. 2016 15:45
- cetis
- Příspěvky: 53
- Škola: MFF UK
- Pozice: student
- Reputace: 0
k-faktor grafu
Zadání:
Které 2k-regulární grafy mají k-faktor?
Bylo mi řečeno, že se na tuto úlohu použije Hallova věta, ale úplně mi není jasné jak. Budu rád za jakoukoliv radu.
Děkuji
Offline
#2 13. 06. 2016 23:53
Re: k-faktor grafu
Hallova věta platí pro bipartitní grafy. Pro 2k-pravidelné bipartitní grafy není problém tvrzení ukázat.
Naopak pro k=1 není těžké najít protipříkald mezi grafy, které nejsou bipartiní.
Offline