Войти
В теории графов убежище - это определенный тип функции на множествах вершин в неориентированном графе. Если убежище существует, его может использовать убегающий, чтобы выиграть игру преследование-уклонение на графе, консультируясь с функцией на каждом этапе игры, чтобы определить безопасный набор вершин для перехода. Хавены были впервые введены Сеймуром и Томасом (1993) как инструмент для характеристики ширины дерева графов. Другие их приложения включают доказательство существования малых разделителей на второстепенных замкнутых семействах графов и характеризацию концов и клики миноры из бесконечных графов.
Если G - неориентированный граф, а X - набор вершин, то X-лоскут - это непустой компонент связности подграфа группы G, образованной удалением X. A haven порядка k в G - это функция β, которая назначает X-лоскут β (X) каждому множеству X из менее чем k вершин. Эта функция также должна удовлетворять дополнительным ограничениям, которые по-разному устанавливаются разными авторами. Число k называется порядком убежища.
В первоначальном определении Сеймура и Томаса убежище требуется для удовлетворения свойства, что каждые два закрылка β (X) и β (Y) должны касаться каждого другое: либо они имеют общую вершину, либо существует ребро с одной конечной точкой в каждой створке. В определении, используемом позже Алоном, Сеймуром и Томасом, убежища вместо этого требуются для удовлетворения более слабого свойства монотонности : если X ⊆ Y, и оба X и Y имеют менее k вершин, то β (Y) ⊆ β (X). Свойство касания подразумевает свойство монотонности, но не обязательно наоборот. Однако из результатов Сеймура и Томаса следует, что в конечных графах, если существует убежище со свойством монотонности, то существует и убежище с таким же порядком и свойством касания.
Ежевика четвертого порядка. Убежище, полученное из этой ежевики, отображает каждое множество X из трех или менее вершин в уникальную связную компоненту G \ X, которая включает по крайней мере один подграф из ежевики. Убежища с определением касания тесно связаны с ежевикой, семейства связанных подграфов данного графа, которые все касаются друг друга. Порядок ежевики - это минимальное количество вершин, необходимое в наборе вершин, который попадает во все подграфы в семействе. Множество закрылков β (X) для убежища порядка k (с определением касания) образует кустарник порядка не меньше k, потому что любой набор Y, содержащий менее k вершин, не может попасть в подграф β (Y). И наоборот, из любой куста ежевики порядка k можно построить убежище того же порядка, определив β (X) (для каждого выбора X) как X-лоскут, который включает в себя все подграфы в кустах, которые не пересекаются. из X. Требование, чтобы все подграфы в ежевике соприкасались друг с другом, может использоваться, чтобы показать, что этот X-закрылки существует, и что все закрылки β (X), выбранные таким образом, касаются друг друга. Таким образом, граф имеет куст порядка k тогда и только тогда, когда он имеет убежище порядка k.
В качестве примера пусть G - сеточный граф с девятью вершинами . Определите убежище порядка 4 в G, сопоставляя каждое множество X из трех или менее вершин с X-закрылком β (X) следующим образом:
Это легко проверить с помощью разбор случая, что эта функция β удовлетворяет требуемому свойству монотонности убежища. Если X ⊆ Y и X имеет менее двух вершин или X имеет две вершины, которые не являются двумя соседями угловой вершины сетки, то существует только один X-створки, и он содержит все Y-створки. В оставшемся случае X состоит из двух соседей угловой вершины и имеет два X-створки: один состоит из этой угловой вершины, а другой (выбран как β (X)), состоящий из шести оставшихся вершин. Независимо от того, какая вершина добавлена к X, чтобы сформировать Y, будет Y-откидная створка по крайней мере с четырьмя вершинами, которая должна быть уникальной самой большой откидной крышкой, поскольку она содержит более половины вершин, не принадлежащих Y. Этот большой Y-образный клапан будет выбран как β (Y) и будет подмножеством β (X). Таким образом, в каждом случае имеет место монотонность.
Гавани моделируют определенный класс стратегий для убегающего в игре преследование-уклонение, в которой менее k преследователей пытаются поймать одного убегающего, как преследователи, так и убегающие ограничены вершинами данного неориентированного графа, а позиции преследователей и убегающих известны обоим игрокам. На каждом ходу игры новый преследователь может быть добавлен в произвольную вершину графа (при условии, что в любой момент времени на графе размещено менее k преследователей), или один из уже добавленных преследователей может быть удален из график. Однако перед добавлением нового преследователя убегающий сначала информируется о своем новом местоположении и может перемещаться по краям графа в любую незанятую вершину. Во время движения убегающий не может проходить ни одну вершину, которая уже занята кем-либо из преследователей.
Если существует k-убежище (со свойством монотонности), то убегающий может избежать захвата на неопределенный срок и выиграть игру, всегда перемещаясь в вершину β (X), где X - это множество вершины, которые будут заняты преследователями в конце хода. Свойство монотонности убежища гарантирует, что при добавлении нового преследователя в вершину графа вершины в β (X) всегда достижимы с текущей позиции убегающего.
Например, убегающий может выиграть эту игру против трех преследователей на сетке 3 × 3, следуя этой стратегии с убежищем порядка 4, описанным в примере. Однако на одном и том же графе четыре преследователя всегда могут поймать убегающего, сначала перейдя на три вершины, которые разделяют сетку на два пути с тремя вершинами, а затем переместятся в центр пути, содержащего убегающего, заставляя убегающего перейти в один из вершины углов и, наконец, удаление одного из преследователей, не примыкающих к этому углу, и размещение его на убегающем. Следовательно, сетка 3 × 3 не может иметь убежища порядка 5.
Убежища со свойством касания позволяют убегающему выиграть игру против более мощных преследователей, которые могут одновременно прыгать с одного набора занятых вершин на другой.
Гавани могут использоваться для характеристики ширины дерева графов: граф имеет убежище порядка k тогда и только тогда, когда он имеет древовидную ширину не менее k - 1. Древовидное разложение может использоваться для описания выигрышной стратегии для преследователей в той же игре преследования-уклонения, поэтому также верно, что граф имеет убежище порядка k тогда и только тогда, когда убегающий выигрывает с лучшей игрой против менее чем k преследователей. В играх, выигранных убегающим, всегда есть оптимальная стратегия в форме, описанной убежищем, а в играх, выигранных преследователем, всегда есть оптимальная стратегия в форме, описанной разложением дерева. Например, поскольку сетка 3 × 3 имеет убежище порядка 4, но не имеет убежища порядка 5, она должна иметь ширину ровно 3. Ту же самую теорему о минимуме и максимуме можно обобщить на бесконечные графы конечной ширины дерева, с определением ширины дерева, в котором базовое дерево должно быть без лучей (то есть не иметь концов ).
Гавани также тесно связаны с существованием разделителей, небольшие множества X вершин в n-вершинном графе такие, что каждый X-лоскут имеет не более 2n / 3. Если граф G не имеет k-вершинного разделителя, то каждое множество X, содержащее не более k вершин, имеет ( уникальный) X-лоскут с более чем 2n / 3 вершинами. В этом случае G имеет убежище порядка k + 1, в котором β (X) определяется как этот единственный большой X-лоскут. То есть каждый граф имеет либо небольшой разделитель, либо убежище высокого порядка.
Если граф G имеет убежище порядка k, где k ≥ hn для некоторого целого h, то G также должен иметь полный граф Khкак несовершеннолетний. Другими словами, Хадвигер число графа с n вершинами и убежищем порядка k не меньше kn. Как следствие, графы без K h без миноров имеют ширину дерева меньше hn и разделители размером меньше hn. В более общем случае ограничение O (√n) на ширину дерева и размер разделителя выполняется для любого нетривиального семейства графов, которое может быть охарактеризовано запрещенными минорами, потому что для любого такого семейства существует константа h такая, что семейство не включать K h.
Если граф G содержит луч, полубесконечный простой путь с начальной вершиной, но без конечной вершины, то он имеет убежище порядка ℵ0 : это есть функция β, которая отображает каждое конечное множество вершин X в X-лоскут, удовлетворяющий условию согласованности убежищ. А именно, определим β (X) как единственный X-лоскут, содержащий бесконечно много вершин луча. Таким образом, в случае бесконечных графов связь между шириной дерева и убежищем нарушается: единственный луч, несмотря на то, что он является деревом, имеет убежища всех конечных порядков и, что еще более важно, убежище порядка ℵ 0. Два луча бесконечного графа считаются эквивалентными, если не существует конечного множества вершин, которое отделяет бесконечно много вершин одного луча от бесконечного количества вершин другого луча; это отношение эквивалентности, и его классы эквивалентности называются концами графа.
Концы любого графа находятся во взаимно однозначном соответствии с его убежищами порядка ℵ 0. Ведь каждый луч определяет убежище, а каждые два эквивалентных луча определяют одно и то же убежище. И наоборот, каждое убежище определяется лучом таким образом, как может быть показано следующим анализом случая:
(где пересечение проходит по всем конечным множествам X) само является бесконечным множеством S, тогда каждый конечный простой путь, заканчивающийся в вершине S, может быть продлен до дополнительной вершины S, и повторение этого процесса расширения дает луч, проходящий через бесконечное количество вершин S. Этот луч определяет данное убежище.
. Если грабитель следует стратегии уклонения, определенной убежищем, а полиция следует стратегии, заданной этой последовательностью наборов, то путь, по которому идет грабитель, образует луч, определяющий убежище.Таким образом, каждый класс эквивалентности лучей определяет уникальное убежище, и каждое убежище определяется классом эквивалентности лучей.
Для любого кардинального числа 
