szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lut 2015, o 19:10 
Użytkownik

Posty: 6
Lokalizacja: Warszawa
Niech G=(V,E) będzie grafem prostym a \alpha - licznością maksymalnej antykliki w tym grafie. Wykazać, że \chi(G)  \ge  |V| / \alpha

Czy ktoś mógłby mi pomóc z tym zadaniem?
Z góry dzięki :)
Pozdrawiam.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
PostNapisane: 13 lut 2015, o 09:18 
Użytkownik
Wierzchołki grafu G możemy podzielić na rozłączne klasy wierzchołków (pokolorowanych tym samym kolorem) V_1 , V_2 , ..., V_{\chi (G)} . Ponieważ, każda taka klasa tworzy antyklikę, więc jej moc nie przekracza liczby \alpha zatem
|V| =|V_1 | +...+|V_{\chi (G)} |\leqslant \sum_{j=1}^{\chi (G) } \alpha  =\alpha \chi (G) .
Góra
Mężczyzna Offline
PostNapisane: 13 lut 2015, o 12:40 
Użytkownik

Posty: 6
Lokalizacja: Warszawa
Dziękuję za pomoc ;-)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba możliwych sposobów - kombinatoryka  kotek881  1
 Liczba 37! jest podzielna przez  jakubzoltowski96  10
 Sekwencje aminokwasów: liczba liczb 17-cyfrowych.  iliadus  2
 Liczba grafów o polu 9-elementowym  Oxford  0
 liczba rozwiązań równania - zadanie 32  ali00491  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl