szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
PostNapisane: 11 sie 2009, o 15:51 
Użytkownik
Udowodnij, że jeśli G jest grafem n-wierzchołkowym, to \chi(G) + \chi (G') \geqslant 2 \sqrt{n}. Podaj przykład nieskończonej rodziny grafów pokazującej, że tego oszacowania nie można wzmocnić.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019
Góra
PostNapisane: 11 sie 2009, o 16:03 
Użytkownik
Dla dowolnych liczb rzeczywistych prawdziwa jest nierówność:
(a+b) ^{2} \ge 4ab
Oznaczenia:
a= \chi (G)
b= \chi (G')
a i b to są liczb dodatnie więc pierwiastkujemy stronami
a+b \ge  2  \sqrt{ab} \ge(*)  \ge 2  \sqrt{n}
CKD
(*)-korzystamy z nierowności :
\chi (G') \cdot \chi (G)  \ge n
jak chcesz to mogę to też udowodnić.

Drugą część zadania już zrobisz?
Góra
PostNapisane: 12 sie 2009, o 16:23 
Użytkownik
Dzięki za pomoc, ale nie wiem jak to skończyć :/ Tzn jak udowodnić tę nierówność i znaleźć rodzinę grafów.
Góra
PostNapisane: 12 sie 2009, o 18:06 
Użytkownik
Żadnego pomysłu?? Może jakieś próby? Bo jak ja Ci wszystko zrobię to niczego się nie nauczysz. Porysuj sobie grafy i zobacz, które grafy pasują nam do zadania. Rysuj cykle, drogi proste, grafy pełne, Eulerowskie , spojne, niespojne itd. Taka metoda będzie bardziej skuteczna niż gotowiec.
Góra
Mężczyzna Offline
PostNapisane: 26 sie 2009, o 23:32 
Użytkownik

Posty: 9834
Lokalizacja: Bydgoszcz
miodzio1988 napisał(a):
\chi (G') \cdot \chi (G)  \ge n

Uznałem, że to byłoby za proste i udowadniałem wyjściową nierówność indukcyjnie.
Ale faktycznie powyższa nierówność zachodzi i to oczywiście wystarcza.

Jej dowód jest prosty - jeśli \chi (G) = k, to po pomalowaniu G na tych k kolorów łatwo zauważyć, że z zasady szufladkowej Dirichleta wynika, że jest przynajmniej \frac{n}{k} wierzchołków jednego koloru. W G' tworzą one klikę, więc do ich pomalowania potrzeba przynajmniej \frac{n}{k} kolorów, zatem przynajmniej tyle wynosi liczba chromatyczna dopełnienia. Zatem żądany iloczyn faktycznie jest równy co najmniej n.

A równość zachodzi gdy G składa się z k klik, każda o k wierzchołkach.

Q.
Góra
PostNapisane: 26 sie 2009, o 23:38 
Użytkownik
Jednak indukcja. Gdybym byl na egzaminie to pewnie też bym tą drogą poszedl. W domu jednak latwiej wpasc na coś sprytnego :P
Fajny dowód :D
No ja się nie uczylem zasady szufladkowej stąd trochę inaczej bym to zrobił. Ale moje wypociny zamieszczę innym razem (edytuję pozniej post), bo dzisiaj to za bardzo padnięty jestem;]
Pozdrawiam.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba chromatyczna - zadanie 5  Anonymous  5
 Liczba chromatyczna - zadanie 2  leszczu450  2
 Liczba chromatyczna - zadanie 4  0Mniac  1
 Liczba chromatyczna - zadanie 6  darex99  1
 Liczba chromatyczna - zadanie 3  psorek12345  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl