#1 13. 12. 2010 12:01
diskretna matematika- grafy
Potrebovala by som pomoc vyriesit tieto ulohy...dakujem
# Určete všechny dvojice (n,k) takové, že existuje k-regulární graf na n vrcholech.
# Nechť G je graf s n vrcholy, jehož každý vrchol má stupeň větší než n/2. Dokažte, že G obsahuje trojúhelník C3.
Offline
#2 13. 12. 2010 14:37
Re: diskretna matematika- grafy
↑ bella:Navrhuji začít tak, že si uvědomíme, které varianty nemohou nastat, protože by se nejednalo o graf a které varianty vyloučí Princip sudosti.
U druhého příkladu existuje mnoho cest. Kterou z nich se půjde velmi závisí na probrané látce. Byl by nějaký odkaz na sylabus předmětu? Na literaturu?
Začal bych takto: vezměme nějaké dva vrcholy spojené hranou. Jaké jsou množiny jejich sousedů?
Offline