Укрытие (теория графов)
Материал из Википедии — свободной encyclopedia
В теории графов укрытие — это определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец, чтобы выиграть игру преследование-уклонение на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти. Укрытия были впервые введены Сеймуром и Томасом[1] как средство характеризации древесной ширины графов[2]. Другие приложения этого понятия — доказательство существования малых сепараторов в замкнутых по минорам семействах графов[3] и описание краёв[англ.] и миноров клик бесконечных графов[4][5].