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.
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 kwadratów w prostokącie  metalknight  9
 Liczba funkcji między zbiorami skończonymi  shadox  10
 Liczba sposobów wrzucenia n kulek *  studciak123  3
 liczba kombinacji 6 cyfrowej liczby parzaystej  swiechu  1
 Ilu jest uczniów w klasie jesli wiadomo że liczba utworzo  Acura_100  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl