В теории графов убежище — это определенный тип функции на множествах вершин в неориентированном графе . Если убежище существует, оно может быть использовано убегающим для победы в игре преследования-уклонения на графе, путем обращения к функции на каждом шаге игры для определения безопасного множества вершин для перемещения. Убежища были впервые введены Сеймуром и Томасом (1993) в качестве инструмента для характеристики древовидной ширины графов. [1] Их другие приложения включают доказательство существования малых сепараторов на замкнутых по минорам семействах графов , [2] и характеристику концов и миноров клик бесконечных графов . [3] [4]
Если G — неориентированный граф, а X — множество вершин, то X -лоскут — это непустой связный компонент подграфа G, образованный удалением X. Убежище порядка k в G — это функция β , которая назначает X -лоскут β ( X ) каждому множеству X из менее чем k вершин. Эта функция также должна удовлетворять дополнительным ограничениям, которые по-разному задаются разными авторами. Число k называется порядком убежища. [5]
В первоначальном определении Сеймура и Томаса [1] требуется убежище, чтобы удовлетворять свойству, что каждые два лоскута β ( X ) и β ( Y ) должны касаться друг друга: либо они имеют общую вершину, либо существует ребро с одной конечной точкой в каждом лоскуте. В определении, использованном позже Алоном, Сеймуром и Томасом [2] , убежища вместо этого должны удовлетворять более слабому свойству монотонности : если X ⊆ Y , и оба X и Y имеют менее k вершин, то β ( Y ) ⊆ β ( X ) . Свойство касания подразумевает свойство монотонности, но не обязательно наоборот. Однако из результатов Сеймура и Томаса [1] следует , что в конечных графах, если существует убежище со свойством монотонности, то также существует убежище с тем же порядком и свойством касания.
Убежища с определением касания тесно связаны с ежевикой , семействами связанных подграфов данного графа, которые все касаются друг друга. Порядок ежевики - это минимальное количество вершин, необходимое в наборе вершин, который затрагивает все подграфы в семействе. Набор лоскутов β ( 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 ) . Таким образом, в каждом случае сохраняется монотонность.
Havens моделируют определенный класс стратегий для убегающего в игре преследования-уклонения , в которой менее k преследователей пытаются поймать одного убегающего, преследователи и убегающий оба ограничены вершинами заданного неориентированного графа, а позиции преследователей и убегающего известны обоим игрокам. На каждом ходу игры новый преследователь может быть добавлен в произвольную вершину графа (при условии, что в любой момент времени на графе размещено менее k преследователей) или один из уже добавленных преследователей может быть удален из графа. Однако перед добавлением нового преследователя убегающий сначала информируется о своем новом местоположении и может перемещаться по ребрам графа в любую незанятую вершину. Во время перемещения убегающий не может проходить через вершину, которая уже занята любым из преследователей.
Если существует k -убежище (со свойством монотонности), то убегающий может избегать поимки бесконечно долго и выиграть игру, всегда перемещаясь в вершину β ( X ), где X — множество вершин, которые будут заняты преследователями в конце хода. Свойство монотонности убежища гарантирует, что при добавлении нового преследователя в вершину графа вершины в β ( X ) всегда будут достижимы из текущей позиции убегающего. [1]
Например, убегающий может выиграть эту игру против трех преследователей на сетке 3 × 3 , следуя этой стратегии с убежищем порядка 4, описанным в примере. Однако на том же графе четыре преследователя всегда могут поймать убегающего, сначала переместившись на три вершины, которые разделяют сетку на два пути по три вершины, затем переместившись в центр пути, содержащего убегающего, загоняя убегающего в одну из угловых вершин и, наконец, удаляя одного из преследователей, который не является смежным с этим углом, и помещая его на убегающего. Следовательно, сетка 3 × 3 не может иметь убежища порядка 5.
Убежища со свойством касания позволяют убегающему выиграть игру против более сильных преследователей, которые могут одновременно перепрыгивать из одного набора занятых вершин в другой. [1]
Убежища могут использоваться для характеристики древовидной ширины графов: граф имеет убежище порядка k тогда и только тогда, когда его древовидная ширина составляет не менее k – 1. Древовидная декомпозиция может использоваться для описания выигрышной стратегии для преследователей в той же игре преследования-уклонения, поэтому также верно, что граф имеет убежище порядка k тогда и только тогда, когда убегающий выигрывает с лучшей игрой против менее чем k преследователей. В играх, выигранных убегающим, всегда существует оптимальная стратегия в форме, описываемой убежищем, а в играх, выигранных преследователем, всегда существует оптимальная стратегия в форме, описываемой древовидной декомпозицией. [1] Например, поскольку сетка 3 × 3 имеет убежище порядка 4, но не имеет убежища порядка 5, она должна иметь ширину дерева ровно 3. Та же теорема о минимуме-максимуме может быть обобщена на бесконечные графы конечной ширины дерева с определением ширины дерева, в котором базовое дерево должно быть безлучевым (то есть не иметь концов ). [1]
Убежища также тесно связаны с существованием сепараторов , небольших наборов X вершин в графе с n вершинами, таких, что каждый X -лоскут имеет не более 2 n ⁄ 3 вершин. Если граф G не имеет k -вершинного сепаратора, то каждый набор X из не более чем k вершин имеет (уникальный) X -лоскут с более чем 2 n ⁄ 3 вершинами. В этом случае G имеет убежище порядка k + 1 , в котором β ( X ) определяется как этот уникальный большой X -лоскут. То есть, каждый граф имеет либо небольшой сепаратор, либо убежище высокого порядка. [2]
Если граф G имеет убежище порядка k , причем k ≥ h 3/2 n 1/2 для некоторого целого числа h , то G также должен иметь полный граф K h в качестве минора . Другими словами, число Хадвигера n- вершинного графа с убежищем порядка k составляет не менее k 2/3 n -1/3 . Как следствие, графы без K h -миноров имеют древесную ширину меньше h 3/2 n 1/2 и сепараторы размером меньше h 3/2 n 1/2 . В более общем случае ограничение на древесную ширину и размер сепаратора выполняется для любого нетривиального семейства графов, которое можно охарактеризовать запрещенными минорами , поскольку для любого такого семейства существует константа h такая, что семейство не включает K h . [2]
Если граф G содержит луч, полубесконечный простой путь с начальной вершиной, но без конечной вершины, то он имеет убежище порядка ℵ 0 : то есть функцию β , которая отображает каждое конечное множество X вершин в X -лоскут, удовлетворяющий условию согласованности для убежищ. А именно, определим β ( X ) как уникальный X -лоскут, который содержит бесконечно много вершин луча. Таким образом, в случае бесконечных графов связь между древовидной шириной и убежищами нарушается: один луч, несмотря на то, что сам является деревом, имеет убежища всех конечных порядков и, что еще сильнее, убежище порядка ℵ 0 . Два луча бесконечного графа считаются эквивалентными, если не существует конечного множества вершин, которое отделяет бесконечно много вершин одного луча от бесконечно многих вершин другого луча; это отношение эквивалентности , и его классы эквивалентности называются концами графа.
Концы любого графа находятся во взаимно-однозначном соответствии с его убежищами порядка ℵ 0 . Ведь каждый луч определяет убежище, и каждые два эквивалентных луча определяют одно и то же убежище. [3] И наоборот, каждое убежище определяется лучом таким образом, как можно показать с помощью следующего анализа случая:
(где пересечение пробегает все конечные множества X ) само по себе является бесконечным множеством S , то каждый конечный простой путь, который заканчивается в вершине S, может быть расширен до достижения дополнительной вершины S , и повторение этого процесса расширения создает луч, проходящий через бесконечное множество вершин S. Этот луч определяет данное убежище.
Таким образом, каждый класс эквивалентности лучей определяет уникальное убежище, а каждое убежище определяется классом эквивалентности лучей.
Для любого кардинального числа бесконечный граф G имеет убежище порядка κ тогда и только тогда, когда он имеет кликовый минор порядка κ . То есть, для несчетных мощностей наибольший порядок убежища в G равен числу Хадвигера графа G. [3 ]
