Сеточная теорема Халина - Halins grid theorem - Wikipedia

В теория графов, раздел математики, Сеточная теорема Халина утверждает, что бесконечные графы с толстые концы являются в точности графы, содержащие подразделения из шестиугольная черепица самолета.[1] Это было опубликовано Рудольф Халин  (1965 ), и является предшественником работы Робертсон и Сеймур связывание ширина дерева к большому сетка несовершеннолетние, который стал важным компонентом алгоритмический теория двумерность.

Определения и заявление

Луч в бесконечном графе - это полубесконечное дорожка: связный бесконечный подграф, в котором одна вершина имеет степень один, а остальные - два.Халин (1964) определены два луча р0 и р1 быть эквивалентным, если существует луч р2 включающий бесконечно много вершин из каждой из них. Это отношение эквивалентности, а его классы эквивалентности (множества взаимно эквивалентных лучей) называются заканчивается графа. Халин (1965) определил толстый конец графа быть концом, содержащим бесконечно много лучей, попарно непересекающийся друг от друга.

Шестиугольная мозаика плоскости

Пример графика с толстым концом дает шестиугольная черепица из Евклидова плоскость. Его вершины и ребра образуют бесконечную кубический планарный граф, в котором много лучей. Например, некоторые его лучи образуют Гамильтоновы пути которые выходят по спирали из центральной начальной вершины и покрывают все вершины графа. Один из этих спиралевидных лучей можно использовать как луч р2 в определении эквивалентности лучей (неважно, какие лучи р0 и р1 приведены), показывая, что любые два луча эквивалентны и что этот граф имеет единственный конец. Также существуют бесконечные наборы лучей, которые не пересекаются друг с другом, например, наборы лучей, которые используют только два из шести направлений, по которым может следовать путь внутри мозаики. Поскольку в нем бесконечно много попарно непересекающихся лучей, все эквивалентные друг другу, этот граф имеет толстый конец.

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

Аналоги для конечных графов

В рамках их работы над граф миноры ведущий к Теорема Робертсона – Сеймура и теорема о структуре графа, Нил Робертсон и Пол Сеймур доказал, что семья F конечных графов имеет неограниченное ширина дерева тогда и только тогда, когда миноры графов в F включать произвольно большой квадрат сеточные графики, или, что то же самое, подграфы шестиугольной мозаики, образованной ее пересечением с произвольно большими дисками. Хотя точное соотношение между шириной дерева и второстепенным размером сетки остается неуловимым, этот результат стал краеугольным камнем в теории двумерность, характеристика определенных параметров графа, которые имеют особенно эффективные управляемый с фиксированными параметрами алгоритмы и схемы полиномиальной аппроксимации.[2]

Для конечных графов ширина дерева всегда на единицу меньше максимального порядка убежище, где убежище описывает определенный тип стратегии грабителя, чтобы сбежать от полиции в преследование-уклонение игра, играемая на графике, и порядок убежища дает количество полицейских, необходимое для поимки грабителя с использованием этой стратегии.[3] Таким образом, связь между шириной дерева и минорами сетки может быть переформулирована: в семействе конечных графов порядок убежищ неограничен тогда и только тогда, когда размер миноров сетки не ограничен. Для бесконечных графов эквивалентность между шириной дерева и порядком убежища больше не верна, но вместо этого убежища тесно связаны с концами: концы графа находятся во взаимно однозначном соответствии с убежищами порядка. ℵ0.[4] Не всегда верно, что бесконечный граф имеет убежище бесконечного порядка тогда и только тогда, когда он имеет второстепенную сетку бесконечного размера, но теорема Халина предоставляет дополнительное условие (толщина конца, соответствующего убежищу), при котором он становится истинный.

Примечания

  1. ^ а б Дистель (2004)
  2. ^ Демейн и Хаджиагайи (2005).
  3. ^ Сеймур и Томас (1993).
  4. ^ Дистель и Кюн (2003).

Рекомендации

  • Демейн, Эрик Д.; Hajiaghayi, MohammadTaghi (2005), "Двумерность: новые связи между алгоритмами FPT и PTAS", Материалы 16-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA) (PDF), стр. 590–601, МИСТЕР  2298309.
  • Дистель, Рейнхард (2004), "Краткое доказательство сеточной теоремы Халина", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, Дои:10.1007 / BF02941538, МИСТЕР  2112834.
  • Дистель, Рейнхард; Кюн, Даниела (2003), "Теоретико-графовые и топологические концы графов", Журнал комбинаторной теории, Серия B, 87 (1): 197–206, Дои:10.1016 / S0095-8956 (02) 00034-5, МИСТЕР  1967888.
  • Халин, Рудольф (1964), "Uber unendliche Wege in Graphen", Mathematische Annalen, 157: 125–137, Дои:10.1007 / bf01362670, HDL:10338.dmlcz / 102294, МИСТЕР  0170340.
  • Халин, Рудольф (1965), "Über die Maximalzahl fremder unendlicher Wege in Graphen", Mathematische Nachrichten, 30: 63–85, Дои:10.1002 / мана.19650300106, МИСТЕР  0190031.
  • Сеймур, Пол Д.; Томас, Робин (1993), «Поиск в графах и теорема о минимуме и максимуме для ширины дерева», Журнал комбинаторной теории, Серия B, 58 (1): 22–33, Дои:10.1006 / jctb.1993.1027.