Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение [ править ]

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

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

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

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

Пример [ править ]

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

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

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

Преследование-уклонение [ править ]

Хэвенс моделирует определенный класс стратегий для убегающего в игре преследование-уклонение, в которой менее 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 не имеет к -vertex сепаратор, то каждое множество X из не более чем K вершин имеет (единственный) X -flap с более чем 2 л / 3 вершин. В этом случае G имеет убежище порядка k + 1 , в котором β ( X ) определяется как это единственное большое X-крышка. То есть у каждого графа есть либо маленький разделитель, либо убежище высокого порядка. [2]

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

В бесконечных графах [ править ]

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

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

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

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

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

Ссылки [ править ]

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