WikiDer > Хейвен (теория графов)

Haven (graph theory)

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

Определение

Если грамм - неориентированный граф, и Икс - множество вершин, то Икс-flap непустой связный компонент подграфа грамм сформированный путем удаления Икс. А убежище порядка k в грамм это функция β который присваивает Икс-крышка β(Икс) к каждому набору Икс менее чем k вершины. Эта функция также должна удовлетворять дополнительным ограничениям, которые по-разному устанавливаются разными авторами. k называется порядок гавани.[5]

В первоначальном определении Сеймура и Томаса[1] убежище требуется для удовлетворения свойства, что каждые два закрылка β(Икс) и β(Y) должны касаться друг друга: либо они имеют общую вершину, либо существует ребро с одной конечной точкой в ​​каждой створке. В определении, которое позже использовали Алон, Сеймур и Томас,[2] вместо этого необходимы убежища для удовлетворения более слабых монотонность свойство: если Икс ⊆ Y, и оба Икс и Y иметь меньше чем k вершины, то β(Y) ⊆ β(Икс). Свойство касания подразумевает свойство монотонности, но не обязательно наоборот. Однако из результатов Сеймура и Томаса следует[1] что в конечных графах, если существует убежище со свойством монотонности, то существует и убежище с таким же порядком и свойством касания.

Ежевика четвертого порядка. Район, полученный из этой ежевики, отображает каждый набор Икс из трех или менее вершин в единственную компоненту связности грамм  Икс который включает по крайней мере один подграф из ежевики.

Убежища с трогательным определением тесно связаны с ежевики, семейства связных подграфов данного графа, которые все касаются друг друга. Порядок ежевики - это минимальное количество вершин, необходимое в наборе вершин, который попадает во все подграфы в семействе. Комплект закрылков β(Икс) для гавани порядка k (с трогательным определением) образует кустарник порядка не менее k, потому что любой набор Y менее чем k вершины не попадают в подграф β(Y). И наоборот, из любого куста порядка k, можно построить убежище того же порядка, определив β(Икс) (для каждого выбора Икс) быть Икс-крышка, включающая в себя все подграфы ежевики, не пересекающиеся сИкс. Требование, чтобы все подграфы в ежевике соприкасались друг с другом, может использоваться, чтобы показать, что это Икс-заблоки есть, и что все закрылки β(Икс) выбранные таким образом соприкасаются друг с другом. Таким образом, граф имеет куст порядка k тогда и только тогда, когда в нем есть убежище порядкаk.

Пример

В качестве примера пусть грамм быть девятивершинным сетка графика. Определите гавань порядка 4 в грамм, отображая каждый набор Икс из трех или менее вершин в Икс-крышка β(Икс), следующее:

  • Если есть уникальный Икс- створка, которая больше любого другого Икс-заслонки, пусть β(Икс) быть таким уникальным большим Икс-крышка.
  • В противном случае выберите β(Икс) произвольно быть любым Икс-крышка.

Легко проверить с помощью анализ случая что эта функция β удовлетворяет требуемому свойству монотонности убежища. Если Икс ⊆ Y и Икс имеет менее двух вершин, или Икс имеет две вершины, которые не являются двумя соседями угловой вершины сетки, то есть только одна Икс-крышка и содержит все Y-крышка. В остальном случае Икс состоит из двух соседей угловой вершины и имеет два Икс-крылки: один состоит из этой угловой вершины, а другой (выбран как β(Икс)) состоящий из шести оставшихся вершин. Независимо от того, какая вершина добавлена ​​к Икс формировать Y, там будет Y-крылок с не менее чем четырьмя вершинами, который должен быть единственным наибольшим закрылком, так как он содержит более половины вершин, не входящих в Y. Этот большой Y-крышка будет выбрана как β(Y) и будет подмножеством β(Икс). Таким образом, в каждом случае имеет место монотонность.

Преследование-уклонение

Гавани моделируют определенный класс стратегий для убегающего в преследование-уклонение игра, в которой меньше чем k преследователи пытаются поймать одного убегающего, и преследователи, и убегающие ограничены вершинами данного неориентированного графа, а позиции преследователей и убегающего известны обоим игрокам. На каждом ходу игры новый преследователь может быть добавлен в произвольную вершину графа (если их число не превышает k преследователи помещаются на график в любое время) или один из уже добавленных преследователей может быть удален с графика. Однако перед добавлением нового преследователя убегающий сначала информируется о своем новом местонахождении и может двигаться по краям графа к любой незанятой вершине. Во время движения убегающий не может проходить ни одну вершину, которая уже занята кем-либо из преследователей.

Если k-haven (со свойством монотонности) существует, тогда убегающий может избежать захвата на неопределенное время и выиграть игру, всегда перемещаясь в вершину β(Икс) куда Икс - множество вершин, которые будут заняты преследователями в конце хода. Свойство монотонности убежища гарантирует, что при добавлении нового преследователя в вершину графа вершины в β(Икс) всегда доступны с текущей позиции убегающего.[1]

Например, убегающий может выиграть эту игру против трех преследователей на 3 × 3 grid, следуя этой стратегии с убежищем порядка 4, описанным в примере. Однако на одном и том же графе четыре преследователя всегда могут поймать убегающего, сначала перейдя на три вершины, которые разделяют сетку на два пути с тремя вершинами, а затем переместятся в центр пути, содержащего убегающего, заставляя убегающего перейти в один из вершины углов и, наконец, удаление одного из преследователей, не примыкающих к этому углу, и размещение его на убегающем. Следовательно 3 × 3 сетка не может иметь убежища порядка 5.

Убежища со свойством касания позволяют убегающему выиграть игру против более сильных преследователей, которые могут одновременно перепрыгивать с одной группы занятых вершин на другую.[1]

Подключения к дереву, разделителям и несовершеннолетним

Гавани могут быть использованы для характеристики ширина дерева графов: у графа есть убежище порядка k если и только если он имеет ширину не менее k − 1. Древовидная декомпозиция может использоваться для описания выигрышной стратегии для преследователей в той же игре преследования и уклонения, поэтому также верно, что граф имеет убежище порядка k тогда и только тогда, когда убегающий выигрывает с лучшей игрой против менее чем k преследователи. В играх, выигранных убегающим, всегда есть оптимальная стратегия в форме, описанной убежищем, а в играх, выигранных преследователем, всегда есть оптимальная стратегия в форме, описанной разложением дерева.[1] Например, потому что 3 × 3 grid имеет убежище порядка 4, но не имеет убежища порядка 5, у него должна быть ширина дерева ровно 3. Та же самая теорема min-max может быть обобщена на бесконечные графы конечной ширины дерева, с определением ширины дерева, в котором базовое дерево должно быть без лучей (то есть не иметь заканчивается).[1]

Гавани также тесно связаны с существованием разделители, малые наборы Икс вершин в п-вершинный граф такой, что каждый Икс-крышка имеет не более 2п/ 3 вершины. Если график грамм не имеет k-вершинный разделитель, затем каждый набор Икс не более k вершин имеет (уникальный) Икс-заслонка с более чем 2п/ 3 вершины. В этом случае, грамм имеет приют порядка k + 1, в котором β(Икс) определяется как этот уникальный большой Икс-крышка. То есть каждый граф имеет либо маленький разделитель, либо убежище высокого порядка.[2]

Если график грамм имеет приют порядка k, с k ≥ час3/2п1/2 для некоторого целого числа час, тогда грамм также должен иметь полный график Kчас как незначительный. Другими словами, Число Хадвигера из п-вершинный граф с убежищем порядка k по крайней мере k2/3п−1/3. Как следствие, Kчас-графы без миноров имеют ширину дерева меньше час3/2п1/2 и разделители размером менее час3/2п1/2. В более общем смысле O (√п) оценка ширины дерева и размера разделителя выполняется для любого нетривиального семейства графов, которое может быть охарактеризовано запрещенные несовершеннолетние, потому что для любой такой семьи существует постоянный час так что семья не включает Kчас.[2]

В бесконечных графах

Если график грамм содержит луч, полубесконечный простой путь с начальной вершиной, но без конечной вершины, тогда он имеет убежище порядка ℵ0: то есть функция β который отображает каждое конечное множество Икс вершин к Икс-крышка, удовлетворяющая условию согласованности убежищ. А именно определить β(Икс) быть уникальным Икс-крышка, содержащая бесконечно много вершин луча. Таким образом, в случае бесконечных графов связь между шириной дерева и убежищем нарушается: единственный луч, несмотря на то, что он является деревом, имеет убежища всех конечных порядков и, что еще более важно, убежище порядка ℵ0. Два луча бесконечного графа считаются эквивалентными, если не существует конечного множества вершин, которые отделяет бесконечно много вершин одного луча из бесконечно большого числа вершин другого луча; это отношение эквивалентности, и это классы эквивалентности называются заканчивается графа.

Концы любого графа находятся во взаимно однозначном соответствии с его убежищами порядка ℵ0. Ведь каждый луч определяет убежище, а каждые два эквивалентных луча определяют одно и то же убежище.[3] И наоборот, каждое убежище определяется таким образом лучом, как может быть показано следующим анализом случая:

  • Если убежище имеет свойство, пересечение (где пересечение пробегает все конечные множества Икс) само является бесконечным множеством S, то каждый конечный простой путь, заканчивающийся вершиной S может быть расширен до дополнительной вершины S, и повторение этого процесса расширения дает луч, проходящий через бесконечно много вершин S. Этот луч определяет данное убежище.
  • С другой стороны, если S конечно, то (работая в подграфе грамм  S) его можно считать пустым. В этом случае для каждого конечного множества Икся вершин существует конечное множество Икся + 1 со свойством, что Икся не пересекается с . Если грабитель следует стратегии уклонения, определяемой убежищем, а полиция следует стратегии, заданной этой последовательностью наборов, то путь, по которому идет грабитель, образует луч, определяющий убежище.[4]

Таким образом, каждый класс эквивалентности лучей определяет уникальное убежище, а каждое убежище определяется классом эквивалентности лучей.

Для любого количественное числительное , бесконечный граф грамм имеет убежище порядка κ тогда и только тогда, когда оно имеет клика незначительный порядка κ. То есть для бесчисленных мощностей наибольший порядок убежища в грамм это Число Хадвигера из грамм.[3]

Рекомендации

  1. ^ а б c d е ж грамм Сеймур, Пол Д.; Томас, Робин (1993), «Поиск в графах и теорема о минимуме и максимуме для ширины дерева», Журнал комбинаторной теории, серия B, 58 (1): 22–33, Дои:10.1006 / jctb.1993.1027.
  2. ^ а б c d Алон, Нога; Сеймур, Пол; Томас, Робин (1990), "Теорема о сепараторе для неплоских графов", J. Amer. Математика. Soc., 3 (4): 801–808, Дои:10.1090 / S0894-0347-1990-1065053-0.
  3. ^ а б c Робертсон, Нил; Сеймур, Пол; Томас, Робин (1991), «Исключение бесконечных несовершеннолетних», Дискретная математика, 95 (1–3): 303–319, Дои:10.1016 / 0012-365X (91) 90343-Z, МИСТЕР 1141945.
  4. ^ а б Дистель, Рейнхард; Кюн, Даниела (2003), "Теоретико-графовые и топологические концы графов", Журнал комбинаторной теории, Серия B, 87 (1): 197–206, Дои:10.1016 / S0095-8956 (02) 00034-5, МИСТЕР 1967888.
  5. ^ Джонсон, Тор.; Робертсон, Нил.; Сеймор, П.; Томас, Робин (2001), "Направленная ширина дерева", Журнал комбинаторной теории, серия B, 82 (1): 138–155, Дои:10.1006 / jctb.2000.2031.