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ć .
[Kombinatoryka] Kombi ze zbiorem dominującym
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.
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.
-
King James
- 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
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.
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.
