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 26. 01. 2022 08:22

El267
Zelenáč
Příspěvky: 3
Škola: PŘF UPOL
Pozice: student
Reputace:   -1 
 

Teorie grafů - důkaz

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

 

#2 28. 01. 2022 00:09 — Editoval laszky (28. 01. 2022 22:10)

laszky
Příspěvky: 2247
Škola: MFF UK, FJFI CVUT
Reputace:   193 
 

Re: Teorie grafů - důkaz

↑ 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

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson