Matematyka.pl

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ć .

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.

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