$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 19 października 2004 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Pawel ŻYLIŃSKI

(Uniwersytet Gdański)

wygłosi referat pod tytułem:

Współpracujące straże - modele i metody

Problem galerii sztuki (ozn. PGS) został sformułowany w 1973 roku przez Victora Klee. Dotyczy on wyznaczenia liczby strażników wystarczającej do strzeżenia galerii w kształcie wielokąta prostego. Strażnik $s$ zdefiniowany jest jako dowolny punkt należący do galerii, który widzi dowolny punkt $p$, o ile odcinek łączący $s$ i $p$ całkowicie zawiera się w wielokącie. Zbiór straży $S$ pokrywa galerię, jeśli każdy punkt galerii widziany jest przez jakąś straż ze zbioru $S$.

Seminarium poświęcone będzie jednemu z wariantów PGS, tzw. problemowi straży współpracujących, w którym wyróżnia się dwa warianty: straże spójne (graf widzialności zbioru straży jest spójny) oraz straże $k$-strzeżone (każda ze straży widziana jest przez przynajmniej $k$ innych straży). W pierwszej części przedstawione zostaną znane wyniki dla każdego z wariantów strzeżenia. Wyniki te dotyczą różnych klas galerii (dowolnego kształtu, ortogonalna, monotoniczna, spiralna, gwia14dzista), fortec oraz krat. Natomiast druga część poświęcona będzie metodom dowodzenia zaprezentowanych rezultatów, a w szczególności pokazaniu interesującego związku pomiędzy problemami czysto geometrycznymi a wybranymi zagadnieniami z teorii grafów.

Serdecznie zapraszamy wszystkich chętnych!