Укрытие (теория графов)

В теории графов укрытие — это определённый тип функции на множествах вершин неориентированного графа. Если укрытие существует, его может использовать беглец, чтобы выиграть игру преследование-уклонение на графе путём использования этой функции на каждом шаге игры для определения безопасных множеств вершин, куда можно перейти. Укрытия были впервые введены Сеймуром и Томасом как средство характеризации древесной ширины графов. Другие приложения этого понятия — доказательство существования малых сепараторов в замкнутых по минорам семействах графов и описание краёв и миноров клик бесконечных графов.

Определение

Если G — неориентированный граф, а X — множество вершин, то X-борт — это непустая связная компонента подграфа графа G, образованная удалением X. Укрытие порядка k в графе G — это функция β, отображающая любое множество X с менее чем k вершинами в X-борт β(X). Эта функция должна также удовлетворять дополнительным ограничениям, которые определяются различным образом различными авторами. Число 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-борт, который больше любого другого X-борта, пусть β(X) будет этим уникальным большим 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 ≥ h^3/2n^1/2 для некоторого целого h, тогда G должен также иметь полный граф K_h в качестве минора. Другими словами, число Хадвигера графа с n вершинами с укрытием порядка k имеет значение, не меньшее k^2/3n^−1/3. Как следствие, свободные от K_h миноров графы имеют древесную ширину, меньшую h^3/2n^1/2 и сепараторы размера, меньшего h^3/2n^1/2. Более обще, граница O(√n) древесной ширины и размер сепаратора выполняется для любого нетривиального семейства графов, которые могут быть охарактеризованы запрещёнными графами, поскольку для любого такого семейства существует константа h, такая, что семейство не включает K_h.

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

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

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

• Если укрытие имеет свойство, что пересечение $S=\bigcap _{X}\left(\beta (X)\cup X\right)$ (где пересечение пробегает по всем конечным множествам X) является само по себе бесконечным множеством S, то любой конечный простой путь, который имеет конечную вершину в S, может быть расширен дополнительной вершиной из S, и повторение процесса расширения даёт луч, проходящий через бесконечное число вершин из S. Это луч определяет заданную укрытие.
• С другой стороны, если S конечно, то (работая с подграфом G \ S) его можно считать пустым. В этом случае для любого конечного множества X_i вершин существует множество X_i + 1 со свойством, что X_i не имеет общих элементов с $X_{i+1}\cup \beta (X_{i+1})$. Если грабитель следует стратегии уклонения, определяемой укрытием, а полиция следует стратегии, задаваемой этой последовательностью множеств, то путь, по которому следует грабитель, образует луч, который определяет укрытие.

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

Для любого кардинального числа $\kappa \geq \aleph _{1}$, бесконечный граф G имеет укрытие порядка κ тогда и только тогда, когда он имеет минор клики порядка κ. То есть для несчётных кардинальных чисел, наибольший порядок укрытия в G является числом Хадвигера графа G.

Литература

• Neil Robertson, Paul Seymour, Robin Thomas. Excluding infinite minors // Discrete Mathematics. — 1991. — Т. 95, вып. 1-3. — С. 303–319. — doi:10.1016/0012-365X(91)90343-Z.
• Reinhard Diestel, Daniela Kühn. Graph-theoretical versus topological ends of graphs // Journal of Combinatorial Theory. — 2003. — Т. 87, вып. 1. — С. 197–206. — doi:10.1016/S0095-8956(02)00034-5.
• Thor Johnson, Neil Robertson, Paul Seymour, Robin Thomas. Directed Tree Width // Journal of Combinatorial Theory, Series B. — 2001. — Т. 82, вып. 1. — С. 138–155. — doi:10.1006/jctb.2000.2031.
• Paul D. Seymour, Robin Thomas. Graph searching and a min-max theorem for tree-width // Journal of Combinatorial Theory, Series B. — 1993. — Т. 58, вып. 1. — С. 22–33. — doi:10.1006/jctb.1993.1027.
• Noga Alon, Paul Seymour, Robin Thomas. A separator theorem for nonplanar graphs // J. Amer. Math. Soc.. — 1990. — Т. 3, вып. 4. — С. 801–808. — doi:10.1090/S0894-0347-1990-1065053-0.