[Kombinatoryka] Kombi ze zbiorem dominującym

Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Awatar użytkownika
Swistak
Użytkownik
Użytkownik
Posty: 1874
Rejestracja: 30 wrz 2007, o 22:04
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 99 razy
Pomógł: 87 razy

[Kombinatoryka] Kombi ze zbiorem dominującym

Post autor: Swistak » 9 sie 2011, o 19:24

Mamy dany sobie graf o \(\displaystyle{ n}\) wierzchołkach taki, że każdy wierzchołek ma stopień co najmniej \(\displaystyle{ d}\). Zbiorem dominującym nazywamy taki zbiór wierzchołków, że każdy wierzchołek grafu ma sąsiada w zbiorze dominującym lub sam do niego należy. Udowodnij, że najmniejszy zbiór dominujący ma rozmiar co najwyżej \(\displaystyle{ \min \left( n \frac{1+\ln \left( 1+d \right) }{1+d}, \ 1+\frac{\ln \ n}{\ln\frac{n}{n-d-1}} \right)}\)

Żeby nie było, to to zadanie wcale nie jest żadnym trollem, pierwsze ograniczenie było wzorcówką, a ja poszedłem trochę innym tropem i udało mi się uzyskać drugie oszacowanie, które dla małych \(\displaystyle{ d}\) jest rzędu \(\displaystyle{ n \log \ n}\) (xDD), a dla całkiem sporych \(\displaystyle{ d}\) jest ograniczeniem istotnie lepszym . Więc naprawdę te rzeczy dają sie zrobić .
Ostatnio zmieniony 21 sie 2011, o 21:26 przez Lbubsazob, łącznie zmieniany 1 raz.
Powód: Poprawa zapisu funkcji.

King James
Użytkownik
Użytkownik
Posty: 150
Rejestracja: 19 kwie 2007, o 22:52
Płeć: Mężczyzna
Lokalizacja: Biłgoraj/Kraków
Pomógł: 39 razy

[Kombinatoryka] Kombi ze zbiorem dominującym

Post autor: King James » 28 sie 2011, o 18:23

Niech \(\displaystyle{ G=(V,E)}\), ustalmy \(\displaystyle{ p \in (0,1)}\), wybierzmy losowo podzbiór wierzchołków \(\displaystyle{ V_1 \subset V}\), przy czym każdy wierzchołek z \(\displaystyle{ V}\) wybieramy niezależnie z prawdopodobieństwem \(\displaystyle{ p}\). Chcemy do naszego \(\displaystyle{ V_1}\) dołożyć wierzchołki, które razem z \(\displaystyle{ V_1}\) będą tworzyły zbiór dominujący, niech więc \(\displaystyle{ V_2}\) będzie zbiorem wierzchołków \(\displaystyle{ v \in V-V_1}\) takich, że \(\displaystyle{ N(v) \cap V_1 = \emptyset}\).

Niech \(\displaystyle{ X, Y}\) będą zmiennymi losowymi oznaczającymi rozmiary odpowiednio \(\displaystyle{ V_1, V_2}\). Pokażemy, że \(\displaystyle{ \mathbf{E}(X+Y) \leq f(p)}\), dla pewnej funkcji \(\displaystyle{ f(p)}\), co będzie implikować istnienie zbioru dominującego wielkości co najwyżej \(\displaystyle{ f(p)}\). Następnie dobierzemy odpowiednio \(\displaystyle{ p}\), tak, żeby \(\displaystyle{ f(p) = n \frac{1+\ln(d+1)}{d+1}}\).

\(\displaystyle{ X}\) ma rozkład dwumianowy, zatem \(\displaystyle{ \mathbf{E}(X) = n p}\), \(\displaystyle{ Y}\) możemy zapisać jako sumę zmiennych indykatorowych \(\displaystyle{ Y = \sum_{v \in V} I_{v \in V_2}}\)

\(\displaystyle{ \mathbf{E}(Y)=\sum_{v \in V} \mathbf{E}(I_{v \in V_2})=\sum_{v \in V} \mathbf{P}(v \in V_2)\leq n(1-p)^{d+1} \leq ne^{-p(d+1)}}\)

przedostatnia nierówność wynika, z tego, że \(\displaystyle{ \mathbf{P}(v \in V_2) = \mathbf{P}(v \cup N(v) \not \in V_1) = (1-p)^{\text{deg}(v)+1} \leq (1-p)^{d+1}}\), ostatnia z \(\displaystyle{ 1-p \leq e^{-p}}\), zatem

\(\displaystyle{ \mathbf{E}(X+Y) = \mathbf{E}(X) + \mathbf{E}(Y) \leq n p + ne^{-p(d+1)} = f(p)}\)

dalej ponieważ \(\displaystyle{ p}\) było ustalone, dla \(\displaystyle{ p = \frac{\ln(d+1)}{d+1}}\) otrzymujemy

\(\displaystyle{ f(\frac{\ln(d+1)}{d+1}) = n \frac{1+\ln(d+1)}{d+1}}\)

Można sprawdzić, że dla naszego \(\displaystyle{ p}\) funkcja \(\displaystyle{ f(p)}\) osiąga wartość najmniejszą. Istnieje też algorytmiczne rozwiązanie wzorcowego oszacowania.

justynian
Użytkownik
Użytkownik
Posty: 705
Rejestracja: 10 lip 2009, o 16:32
Płeć: Mężczyzna
Podziękował: 21 razy
Pomógł: 58 razy

[Kombinatoryka] Kombi ze zbiorem dominującym

Post autor: justynian » 28 sie 2011, o 22:06

Można wiedzieć skąd jest ten problem ?

ODPOWIEDZ