Jakub PRZYBYŁO

(WMS AGH)

Strażnicy, zasysacze i zbiory wielokrotnie dominujące

Podzbiór $D$ zbioru wierzchołków $V$ grafu prostego $G$ nazywamy zbiorem dominującym, jeżeli $N[v]\cap D\ge 1$ dla każdego wierzchołka $v\in V$, gdzie przez $N[v]$ rozumiemy domknięte sąsiedztwo wierzchołka v, tj., $N[v]:=\{v\}\cup N(v)$. Najmniejszy rozmiar zbioru dominującego dla grafu $G$ nazywamy liczbą dominującą i oznaczamy przez $\gamma(G)$. Fundamentalnym wynikiem dającym ,,asymptotycznie optymalne'' ograniczenie na ten parametr jest wynik Alona i Spencera, osiągnięty także niezależnie w kilku innych pracach, mówiący, że:

$$\gamma(G)\le \frac{\ln(\delta+1)+1}{\delta +1}.$$

Przedstawiony zostanie dowód tego faktu oraz jego uogólnienia na przypadek zbiorów wielokrotnie dominujących. W konsekwencji otrzymamy także ograniczenia na liczbę elementów (strażników) dla pewnych zagadnień zbiorów dominujących (lub systemów strażników) odpornych na błędy. Wykorzystane zostaną zarówno metody standardowe, obejmujące wykorzystanie algorytmu zachłannego w jednoosobowej ,,grze o zasysaczach'', jak i podejście probabilistyczne.

Serdecznie zapraszamy wszystkich chętnych !