5.06.2008

Problem galerii sztuki w kratach i pokrewne problemy grafowe

Problem strzeżenia krat jest jednym z wariantów Problemu Galerii Sztuki (V. Klee, 1973) i został sformułowany przez S. Ntafosa w 1986 roku. Kratę definiujemy jako zbiór wszystkich punktów należących do (danego) zbioru pionowych i poziomych odcinków; na kratę można patrzeć jak na wielokąt ortogonalny z dziurami składający się z bardzo wąskich korytarzy. Mówimy, ze dwa punkty x i y należące do kraty widza się nawzajem, jeśli odcinek łączący te punkty zawiera się w kracie. Podczas referatu omówione zostaną rożne modele strzeżenia krat (m.in. strażnicy współpracujący i słabo współpracujący, strażnicy mobilni oraz problem gonitwy i ucieczki) oraz ich związki z podstawowymi problemami teorii grafów (skojarzenia, kolorowanie, dominowanie).