Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 07. 06. 2016 15:45

cetis
Příspěvky: 53
Škola: MFF UK
Pozice: student
Reputace:   
 

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

petrkovar
Veterán
Místo: Ostrava/Krmelín
Příspěvky: 1012
Pozice: VŠB - TU Ostrava
Reputace:   23 
Web
 

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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson