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

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

Определение

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

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

Ежевика порядка четыре. Укрытие, полученное из этой ежевики, отображает каждое множество 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) всегда будут доступны из текущего положения беглеца[2].

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

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

Связь с древесной шириной, сепараторами и минорами

Укрытия могут быть использованы для описания древесной ширины графа — граф имеет укрытие порядка k тогда и только тогда, когда он имеет древесную ширину по меньшей мере k − 1. Древесная декомпозиция может быть использована для описания выигрышной стратегии для преследователей в той же игре преследования-уклонения, так что верно утверждение, что граф имеет укрытие порядка k тогда и только тогда, когда беглец выигрывает при правильной игре против менее чем k преследователей. В играх, выигрываемых беглецом, всегда существует оптимальная стратегия в виде укрытия, а в играх, выигрываемых преследователями, всегда существует оптимальная стратегия в виде древесной декомпозиции[2]. Например, поскольку решётка 3 × 3 имеет укрытие порядка 4, но не имеет укрытия порядка 5, она должна иметь древесную ширину, в точности равную 3. Та же минимаксная теорема может быть обобщена на бесконечные графы с конечной древесной шириной, если в определении древесной ширины от лежащего в основе дерева требуется отсутствие концов^[англ.][2].

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

Если граф 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[3].

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

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

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

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

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

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

Примечания

1. Seymour, Thomas, 1993.
2. Seymour, Thomas, 1993, с. 22–33.
3. Alon, Seymour, Thomas, 1990, с. 801–808.
4. Robertson, Seymour, Thomas, 1991, с. 303–319.
5. Diestel, Kühn, 2003, с. 197–206.
6. Johnson, Robertson, Seymour, Thomas, 2001, с. 138–155.

Литература

• 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.