#1 13. 12. 2012 21:13
Teoria grafov - dôkaz
Vedel by mi niekto pomôcť s týmto dôkazom?
Nech k je dĺžka najdlhšej cesty v grafe G. Dokážte, že 
(G) 
k+1
Potrebujem to čo najskôr. Potrebujem to dokázať číselne nie graficky.
Skúšala som to hľadať aj na internete a nikde som to nenašla.
Spísala som si k tomu vzorce.
Možno pomôže že vo všeobecnosti platí, že: (G) je chromatické číslo, čo najmenej farieb vrcholov, aby hrana obsahovala vrcholy rôznej farby 
(G) je maximálny stupeň v grafe
Offline
#2 14. 12. 2012 00:44
Re: Teoria grafov - dôkaz
Doporučuji následující postup:
Označit 
největší nezávislou množinu vrcholů v daném grafu. (V nezávislé množině vrcholů nejsou žádné dva vrcholy spojeny hranou v původním grafu). Tyto vrcholy můžeme obarvit barvou 1. (Proč?)
Všechny vrcholy z grafu odstraníme a zkusíme postup opakovat.
Po konečném počtu kroků postup jistě končí (proč?) a zbývá argumentovat, že počet kroků můžeme shora odhadnout délkou nejdelší cesty v grafu.
Offline
#4 15. 12. 2012 15:29
Re: Teoria grafov - dôkaz
↑ rado111:Ne, není nutno argumentaci vést nad konkrétním grafem. Zkrátka označíme největší nezávislou množinu vrcholů v nějakém grafu (nemáme jeden konkrétní graf).
A jak příjdete na nejdelší cestu? Dá se rozmyslet a (a zdůvodnit proč) je každý vrchol v množině 
sousední s nějakým vrcholem v množině 
. Nápověda: tady se využije toho, že v~každém kroku vezmeme největší množinu nezávislých vrcholů.
Offline
#5 15. 12. 2012 18:47
Re: Teoria grafov - dôkaz
No takže nájdem najväčšiu nezávislú množinu vrcholov hej? No, tak hľadám chromatické číslo.....nie?.....a ked nájdem chromatické číslo tak potom ako zistím najdlhšiu cestu v grafe?Či ako?...a aj tak nechápem ako....:( Lebo ked nemám konkrétny graf tak potom ani neviem ako mám hľadať tú najväčšiu nezávislú množinu vrcholov :(
Offline
#6 15. 12. 2012 18:51
Re: Teoria grafov - dôkaz
Ja jsem z toho jelen. Nemohol by ste mi to nejak celkovo vyriesit lebo už sa to pokúšam spraviť asi mesiac a netušim ako sa to robí. Bol by som Vám veľmi vďačný....nejak na papir na pisat a potom mi to nejak oskenovat a poslat ?
Offline
#7 15. 12. 2012 20:35
Re: Teoria grafov - dôkaz
↑ rado111:Dodat kompletní řešení není smyslem tohoto fóra (pravidlo 3), takže se vrátím k řešení příkladu.
Tím, že najdete největší nezávislou množinu vrcholů, neurčíme chomatické číslo grafu. V jistém smyslu je to "naopak". Všechny vrcholy (největší) nezávislé množiny vrcholů mohou mít stejnou barvu, protože jsou nezávislé. Jde o to, kolik těch množin najdeme. Jejich počet je jistě větší něž chromatické číslo grafu (proč?) a naopak se dá ukázat (naznačuji v předchozím příspěvu), že jich je méně než je délka nejdelší cesty v grafu.
Když se zargumentují chybějící detaily celého postupu, který jsem tu popsal, tak dostaneme hledaný důkaz.
Ještě jedna poznámka:
největší nezávislou množinu vrcholů nemusíme "hledat", ale předpokládáme, že v daném grafu postě "je". Uvedený důkaz je proto existenční, nikoliv konstruktivní. Důkaz to však pořád je. Není třeba nic "vypčítat". Jen ukážeme platnost nějakých nerovností.
Offline
#9 18. 12. 2012 23:10
Re: Teoria grafov - dôkaz
↑ rado111:Nejdelší cestu není třeba hledat. Je jasné, že nejdelší cesta je delší, než Počet množin V_1, V_2, ..., V_l. Toto je klíčvé při argumentaci v důkazu.
Offline