szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
PostNapisane: 18 sie 2015, o 17:07 
Użytkownik
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} ?
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 10:51 
Gość Specjalny

Posty: 5872
Lokalizacja: Toruń
Używasz jakichś nieklasycznych oznaczeń?
Rozumiem, że X(G) = \chi (G)? Czym jest \beta_0?
Góra
PostNapisane: 19 sie 2015, o 10:54 
Użytkownik
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 10:55 
Gość Specjalny

Posty: 5872
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
PostNapisane: 19 sie 2015, o 11:05 
Użytkownik
Co oznacza najlepsze kolorowanie? Że używamy jak najmniej kolorów?
Góra
Mężczyzna Offline
PostNapisane: 19 sie 2015, o 11:34 
Gość Specjalny

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


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Liczba sposobów.. -- zadanie  anulka  2
 Liczba permutacji ciągu znaków  Anon123Pl  1
 Liczba liczb sześciocyfrowych.  Suvi  2
 Liczba ciągów z parzystą liczbą wystąpień litery.  kolar  0
 Liczby pięciocyfrowe, liczba podzbiorów  andziamis  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl