szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 12 lut 2015, o 18: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.
Góra
PostNapisane: 13 lut 2015, o 08: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 11: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 ośmiocyfrowa - zadanie 2  krystian1863  2
 Liczba elementów odwracalnych, funkcja Eulera  Scoler  5
 Liczba możliwych kodów  Glo  0
 Liczba podzbiorów  Andrzejmm  2
 liczba stirlinga 2 rodzaju  Majka99  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl