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 21. 04. 2020 17:23 — Editoval ann70 (21. 04. 2020 18:08)

ann70
Zelenáč
Příspěvky: 12
Reputace:   
 

Vrcholové zafarbenia grafov

Dobrý deň,

vedeli by ste mi niekto prosím Vás poradiť ako postupovať pri takomto dôkaz?

Nech G je graf na n vrcholoch s m hranami. Dokážte, že χ(G)≥n^2/(n^2−2m).

Ďakujem

Offline

 

#2 23. 04. 2020 03:27

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

Re: Vrcholové zafarbenia grafov

Ahoj, ja bych zacal tak, ze bych si rozmyslel, jak vypada graf, ktery pro dane X(G) a n ma maximalni pocet hran.
Dosel bych k zaveru, ze takovy graf ma priblizne stejny pocet vrcholu (p nebo p+1) ruznych barev, tj

$n=p\cdot\chi(G)+q,\; \mbox{kde}\ 0\leq q\leq \chi(G)-1$

a vsechny ruzne barevne vrcholy jsou spojeny. Pocet hran, ktere chybi do uplneho grafu je pak rovny poctu hran,
ktere je nutno pridat mezi stejnebarevne vrcholy a plati tedy odhad

$\binom{n}{2}-m \;\; \geq \;\;  \bigr(\chi(G)-q\bigr)\cdot\binom{p}{2} + q\cdot\binom{p+1}{2}$

Dosadime-li za $q=n-p\cdot\chi(G)$, ziskame

$\binom{n}{2}-m \;\; \geq \;\;  \bigr((p+1)\cdot\chi(G)-n\bigr)\cdot\binom{p}{2} + \bigr(n-p\cdot\chi(G)\bigr)\cdot\binom{p+1}{2}$

coz lze prepsat na

$n^2-2m \;\; \geq\;\; n+2pn-p^2\cdot\chi(G)-p\cdot\chi(G)$

a staci tedy ukazat, ze plati

$n+2pn-p^2\cdot\chi(G)-p\cdot\chi(G)\;\; \geq\;\; \frac{n^2}{\chi(G)}$

coz lze zapsat jako

$\bigr(n-p\cdot\chi(G)\bigr)\left(p+1-\frac{n}{\chi(G)}\right)\;\;\geq\;\;0$

Prvni zavorka je rovna $q$ a je urcite nezaporna, druha zavorka je rovna $1-\frac{q}{\chi(G)}\geq \frac{1}{\chi(G)}>0$.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson