Mateusz NIKODEM

(WMS AGH oraz WMiI UJ)

O zbiorach dominujących odpornych na błędy

Niech $S\subset V(G)$ będzie zbiorem dominującym w grafie G, tzn. takim, że dla każdego $v \in V(G)$ zachodzi $N[v]\cap S \not = \emptyset$. Zbiór ten można interpretować jako system czujników lub strażników kontrolujących daną strukturę dającą się przedstawić w formie grafu. Chcemy, aby system kontroli był sprawny, nawet gdy wiemy, że pewna (ustalona) liczba czujników działa nieprawidłowo. Nieprawidłowościami mogą być brak reakcji podczas awarii, błędne wskazanie miejsca awarii lub niezasadne zgłoszenie awarii. Zagadnienie można więc interpretować również jako problem leniwych i kłamliwych lub nadgorliwych strażników. Przedstawione zostaną pewne warunki konieczne i wystarczające na to, by zbiór $S$ był sprawnym systemem kontroli.

Serdecznie zapraszamy wszystkich chętnych !