Введение

Метод разложения графов В теории графов, гаван - это определенный тип функции на множествах вершин в ненаправленном графе. Если убежище существует, то его можно использовать для победы в игре преследования/ухода на графике, проконсультировавшись с функцией на каждом этапе игры, чтобы определить безопасный набор вершин, в которые можно переместиться. Порты были впервые введены в качестве инструмента для характеристики древесной ширины графов.

Определение

Если G - ненаправленный граф, а X - множество вершин, то X-клапан - это непустой связанный компонент подграфа G, образованный удалением X. Прибежище порядка k в G - это функция β, которая присваивает X-клапан β(X) каждому множеству X, имеющему меньше k вершин. Эта функция также должна удовлетворять дополнительным ограничениям, которые по-разному даны разными авторами. Число k называется порядком убежища. В первоначальном определении Сеймура и Томаса, убежище требуется для удовлетворения свойства, что каждые два клапана β ((X) и β ((Y) должны касаться друг друга: либо они имеют общую вершину, либо существует край с одной конечной точкой в каждом клапане. В определении, используемом позже Алоном, Сеймуром и Томасом, если граф G имеет убежище порядка k, с для некоторого целого числа h, то G также должен иметь полный граф в качестве второстепенного. Другими словами, число Хадвигера графа с n вершинами с убежищем порядка k составляет по меньшей мере . Следовательно, у свободных графов меньшего размера есть ширина дерева меньше, чем и разделители размером меньше . Более общего O ((\sqrt{n}) связанная шириной дерева и разделительным размером имеет значение для любого нетривиального семейства графов, которые могут быть характеризованы запрещенными несовершеннолетними, потому что для любой такой семьи существует постоянная h, которую семья не включает .

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

Если граф G содержит луч, полубесконечный простой путь с начальной вершиной, но без конечной вершины, то он имеет пристанище порядка: то есть функцию β, которая отображает каждый конечный набор X вершин на X-клапан, удовлетворяя условию согласованности для убежищ. А именно, определите β(X) как уникальный X-клапан, который содержит бесконечно много вершин луча. Таким образом, в случае бесконечных графов связь между древоширием и гаванями нарушается: один луч, несмотря на то, что он сам является деревом, имеет гаваники всех конечных порядков и даже более сильный приют порядка Два луча бесконечного графа считаются эквивалентными, если нет конечного набора вершин, которые отделяют бесконечно много вершин одного луча от бесконечно много вершин другого луча; это отношение эквивалентности, и его классы эквивалентности называются концами графа. Концы любого графа находятся в одно к одному соответствии с его убежищами порядка, так как каждый луч определяет убежище, и каждые два эквивалентных луча определяют тот же самый убежище. И наоборот, каждый рай определяется лучем таким образом, как можно показать следующим анализом случая: если рай имеет свойство, что пересечение (где пересечение простирается на все конечные множества X) само по себе является бесконечным множеством S, то каждый конечный простой путь, который заканчивается вершиной S, может быть расширен, чтобы достичь дополнительной вершины S, и повторение этого процесса расширения производит луч, проходящий через бесконечно много вершин S. Этот луч определяет данный рай. С другой стороны, если S конечен, то (работая в подграфе G \ S) можно предположить, что он пуст. В этом случае для каждого конечного множества вершин есть конечный набор с свойством, которое является разъединенным от Если грабитель следует стратегии уклонения, определенной убежищем, и полиция следует стратегии, данной этой последовательностью наборов, то путь, пройденный грабителем, образует луч, который определяет убежище. Таким образом, каждый эквивалентный класс лучей определяет уникальный рай, и каждый рай определяется эквивалентным классом лучей. Для любого кардинального числа бесконечный граф G имеет место порядка κ , если и только если у него есть минора клики порядка κ . То есть, для бесчисленных кардинальностей, наибольший порядок гавана в G является числом Гадвигера G.