szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 18 sie 2015, o 18:07 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
1.Jeśli G jest grafem k-regularnym o p wierzchołkach to
X(G) \ge  \frac{p}{p-k}

2. Dla każdego grafu G o p wierzchołkach X(G)X'(G ) \ge p.

W pierwszym zadaniu próbowałem wyjść ze znanej nierówności:
\frac{p}{ \beta _{0}}  \le X(G) \le p- \beta _{0}+1

Wystarczy więc wykazać, że
p-k \ge  \beta _{0} ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 11:51 
Gość Specjalny

Posty: 5710
Lokalizacja: Toruń
Używasz jakichś nieklasycznych oznaczeń?
Rozumiem, że X(G) = \chi (G)? Czym jest \beta_0?
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 11:54 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Tak, powinno być \chi. \beta _{0} jest największą licznością niezależnego zbioru wierzchołków.
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 11:55 
Gość Specjalny

Posty: 5710
Lokalizacja: Toruń
Odnośnie 2, rozumiem, że miało być \chi(G) \chi (G') \geq p

Niech V_1, V_2, \ldots będzie rozbiciem V odpowiadającym najlepszemu kolorowaniu G. Każdy z tych zbiorów jest kliką w G', więc
\chi(G') \geq \max \{ |V_j| \ : j=1,\ldots, \chi(G) \} \geq \frac{p}{\chi(G)},
co kończy dowód.
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 12:05 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Co oznacza najlepsze kolorowanie? Że używamy jak najmniej kolorów?
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 12:34 
Gość Specjalny

Posty: 5710
Lokalizacja: Toruń
Tak
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 dziesięciocyfrowa liczba  micsko123  4
 Rozspójnianie grafu - zadanie 18  moncq  1
 liczba wszystkich mozliwych wynikow ....  Smakuś  1
 Liczba relacji - zadanie 2  Sylakenth  1
 Liczba chromatyczna - zadanie 3  psorek12345  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl