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

Определение

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

В первоначальном определении Сеймура и Томаса укрытия требуется выполнение свойства, что любые два борта β ( X ) и β ( Y ) должны касаться друг друга — либо они должны иметь общую вершину, либо должно существовать ребро, концы которого принадлежат этим двум бортам. В определении, использованном позднее Алоном, Сеймуром и Томасом , для укрытия требуется удовлетворение более слабого свойства монотонности — если X ⊆ Y и оба множества, как X , так и Y , имеют меньше, чем k вершин, то β ( Y ) ⊆ β ( 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 -борт имеет максимум 2 n /3 вершин. Если граф G не имеет сепаратора с k вершинами, то любое множество X с максимум k вершинами имеет (уникальный) X -борт с более чем 2 n /3 вершинами. В этом случае G имеет укрытие порядка k + 1 , в котором β ( X ) определяется как уникальный большой X -борт. То есть любой граф имеет либо малый сепаратор, либо укрытие высокого порядка .

Если граф G имеет укрытие порядка k , при k ≥ h ^3/2 n ^1/2 для некоторого целого h , тогда G должен также иметь полный граф K _h в качестве минора . Другими словами, число Хадвигера графа с n вершинами с укрытием порядка k имеет значение, не меньшее k ^2/3 n ^−1/3 . Как следствие, свободные от K _h миноров графы имеют древесную ширину, меньшую h ^3/2 n ^1/2 и сепараторы размера, меньшего h ^3/2 n ^1/2 . Более обще, граница O(√ n ) древесной ширины и размер сепаратора выполняется для любого нетривиального семейства графов, которые могут быть охарактеризованы запрещёнными графами , поскольку для любого такого семейства существует константа h , такая, что семейство не включает K _h .

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

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

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

• Если укрытие имеет свойство, что пересечение ${\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})}$ . Если грабитель следует стратегии уклонения, определяемой укрытием, а полиция следует стратегии, задаваемой этой последовательностью множеств, то путь, по которому следует грабитель, образует луч, который определяет укрытие .

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

Для любого кардинального числа ${\displaystyle \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 : .
• Reinhard Diestel, Daniela Kühn. Graph-theoretical versus topological ends of graphs // Journal of Combinatorial Theory . — 2003. — Т. 87 , вып. 1 . — С. 197–206 . — doi : .
• Thor Johnson, Neil Robertson, Paul Seymour, Robin Thomas. Directed Tree Width // Journal of Combinatorial Theory, Series B . — 2001. — Т. 82 , вып. 1 . — С. 138–155 . — doi : .
• 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 : .
• Noga Alon, Paul Seymour, Robin Thomas. A separator theorem for nonplanar graphs // J. Amer. Math. Soc.. — 1990. — Т. 3 , вып. 4 . — С. 801–808 . — doi : .