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
Zdravím, chtěla jsem Vás moc poprosit o pomoc s řešením jednoho příkladu z teorie grafů. Bohužel si s tímto už opravdu nevím rady a proto jsem se rozhodla zkusit napsat i sem Vám, jestli by Vás něco nenapadlo 🙁
Příklad: Nechť G je n vrcholový graf, n>=2, splňující chromatické číslo chí(G)=n-1. Dokažte, že pro klikové číslo grafu G platí omega(G)=n-1.
Offline
↑ El267:
Ahoj, rozlis pripady, kdy [mathjax]G[/mathjax] je souvisly a kdy neni souvisly:
I) [mathjax]G[/mathjax] je souvisly
Postupuj indukci vzhledem k [mathjax]n[/mathjax]. Ukaz, ze to plati pro [mathjax]n=3[/mathjax] (pro [mathjax]n=2[/mathjax] neexistuje souvisly graf splnujici predpoklad [mathjax]\chi(G)=1[/mathjax]). Predpokladej, ze tvrzeni plati pro vsechny grafy, ktere maji pocet vrcholu [mathjax]n-1[/mathjax] a chromaticke cislo [mathjax]n-2[/mathjax], a uvazuj graf [mathjax]G[/mathjax] na [mathjax]n[/mathjax] vrcholech s [mathjax]\chi(G)=n-1[/mathjax]. Zrejme graf [mathjax]G[/mathjax] neni uplny (jinak by mel [mathjax]\chi(G)=n[/mathjax]) a nejedna se ani o kruznici liche delky (ta ma [mathjax]\chi(G)=3=n-1[/mathjax], takze by muselo byt [mathjax]n=4[/mathjax], coz neni liche). Podle Brooksovy vety (plati jen pro souvisle grafy, takze proto to rozliseni na souvisle a nesouvisle grafy) je tedy [mathjax] \Delta(G) \geq \chi(G) = n-1[/mathjax]. V grafu [mathjax]G[/mathjax] proto existuje vrchol [mathjax]v[/mathjax] se stupnem [mathjax]\mathrm{deg}_G(v)=n-1[/mathjax], tj vrchol spojeny se vsemi ostatnimi vrcholy. Pri obarveni grafu [mathjax]G[/mathjax] pomoci [mathjax]n-1[/mathjax] barev je tedy barva vrcholu [mathjax]v[/mathjax] odlisna od barev vsech ostatnich vrcholu. Odebereme-li nyni vrchol [mathjax]v[/mathjax], ziskame graf [mathjax]\widetilde{G}=G\setminus v[/mathjax], pro ktery plati [mathjax]\chi(\widetilde{G})=n-2.[/mathjax] Podle indukcniho predpokladu je [mathjax]\omega(\widetilde{G})=n-2[/mathjax] a v grafu [mathjax]\widetilde{G}[/mathjax] tedy existuje klika velikosti [mathjax]n-2[/mathjax]. To ale znamena, ze v puvodnim grafu [mathjax]G[/mathjax] musela existovat klika velikosti alespon [mathjax]n-1[/mathjax]. Vrchol [mathjax]v[/mathjax] byl totiz spojen se vsemi zbylymi vrcholy. Tedy [mathjax]\omega(G)\geq n-1[/mathjax]. Protoze [mathjax]G[/mathjax] neni uplny, musi byt [mathjax]\omega(G)\leq n-1[/mathjax], a proto [mathjax]\omega(G)= n-1[/mathjax].
II) [mathjax]G[/mathjax] neni souvisly
Jelikoz je [mathjax]\chi(G)=n-1[/mathjax], musi graf [mathjax]G[/mathjax] obsahovat komponentu s alespon [mathjax]n-1[/mathjax] vrcholy. Jinak by nutne bylo [mathjax]\chi(G)<n-1[/mathjax]. Zaroven nemuze obsahovat komponentu s vice nez [mathjax]n-1[/mathjax] vrcholy, protoze by pak byl souvisly. Graf [mathjax]G[/mathjax] je tedy tvoren dvema komponentami - izolovanym vrcholem a komponentou majici [mathjax]n-1[/mathjax] vrcholu. Protoze je ale [mathjax]\chi(G)=n-1[/mathjax], je [mathjax](n-1)[/mathjax]-prvkova komponenta uplnym podgrafem - tedy klikou. A proto je [mathjax]\omega(G)= n-1[/mathjax].
Offline