В теории графов , раздел математики, теорема сетки Халин в утверждает , что бесконечные графы с толстыми концами в точности графа , содержащие подразделения на гексагональной черепице плоскости. [1] Он был опубликован Рудольфом Халином ( 1965 ) и является предшественником работы Робертсона и Сеймура, связывающей ширину дерева с большими минорами сетки , которая стала важным компонентом алгоритмической теории двумерности .
Определения и заявление
Луч в бесконечном графе - это полубесконечный путь : связный бесконечный подграф, в котором одна вершина имеет степень один, а остальные - степень два. Халин (1964) определил два луча r 0 и r 1 как эквивалентные, если существует луч r 2, который включает бесконечно много вершин из каждого из них. Это отношение эквивалентности , и его классы эквивалентности (множества взаимно эквивалентных лучей) называются концами графа. Халин (1965) определил толстый конец графа как конец, содержащий бесконечно много лучей, попарно не пересекающихся друг с другом.
Пример графа с толстым концом обеспечивается гексагональной черепицей на евклидовой плоскости . Его вершины и ребра образуют бесконечный кубический планарный граф , содержащий множество лучей. Например, некоторые из его лучей образуют гамильтоновы пути, которые расходятся по спирали из центральной начальной вершины и покрывают все вершины графа. Один из этих спиралевидных лучей может использоваться в качестве луча r 2 в определении эквивалентности лучей (независимо от того, какие лучи r 0 и r 1 даны), показывая, что каждые два луча эквивалентны и что этот граф имеет единственный конец. Также существуют бесконечные наборы лучей, которые не пересекаются друг с другом, например, наборы лучей, использующие только два из шести направлений, по которым может следовать путь внутри мозаики. Поскольку в нем бесконечно много попарно непересекающихся лучей, эквивалентных друг другу, этот граф имеет толстый конец.
Теорема Халина утверждает, что этот пример универсален: каждый граф с толстым концом содержит в качестве подграфа либо сам этот граф, либо граф, образованный из него путем его простых изменений, путем разделения некоторых его ребер на конечные пути. Подграф этой формы можно выбрать так, чтобы его лучи принадлежали данному толстому концу. И наоборот, всякий раз, когда бесконечный граф содержит подразделение гексагональной мозаики, он должен иметь толстый конец, а именно конец, содержащий все лучи, являющиеся подграфами этого подразделения. [1]
Аналоги для конечных графов
В рамках своей работы над минорами графов, приводящей к теореме Робертсона – Сеймура и теореме о структуре графов , Нил Робертсон и Пол Сеймур доказали, что семейство конечных графов F имеет неограниченную древесную ширину тогда и только тогда, когда миноры графов в F включают произвольно большие графы с квадратной сеткой или, что то же самое, подграфы шестиугольной мозаики, образованной пересечением ее с произвольно большими дисками. Хотя точное соотношение между шириной дерева и второстепенным размером сетки остается неуловимым, этот результат стал краеугольным камнем в теории двумерности , характеризации определенных параметров графа, которые имеют особенно эффективные алгоритмы обработки с фиксированными параметрами и схемы аппроксимации за полиномиальное время . [2]
Для конечных графов ширина дерева всегда на единицу меньше максимального порядка убежища , где убежище описывает определенный тип стратегии грабителя, чтобы убежать от полиции в игре преследования-уклонения, играемой на графе, и порядок следования. Haven дает количество полицейских, необходимое для поимки грабителя с помощью этой стратегии. [3] Таким образом, связь между шириной дерева и минорами сетки может быть переформулирована: в семействе конечных графов порядок убежищ неограничен тогда и только тогда, когда размер миноров сетки неограничен. Для бесконечных графов, эквивалентность между древесная шириной и порядка убежища больше не верно, но вместо этого убежища тесно связаны с концами: концы графа , не находятся во взаимно однозначное соответствие с убежищами порядка ℵ 0 . [4] Не всегда верно, что бесконечный граф имеет убежище бесконечного порядка тогда и только тогда, когда он имеет второстепенную сетку бесконечного размера, но теорема Халина предоставляет дополнительное условие (толщина конца, соответствующего убежищу) при что становится правдой.
Заметки
- ^ а б Дистель (2004)
- ^ Demaine & Hajiaghayi (2005) .
- ^ Сеймур и Томас (1993) .
- ^ Diestel & Кюн (2003) .
Рекомендации
- Демейн, Эрик Д .; Hajiaghayi, MohammadTaghi (2005), «Двумерность: новые связи между алгоритмами FPT и PTAS», Труды 16-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA) (PDF) , стр. 590–601, MR 2298309.
- Diestel Рейнхард (2004), "Короткое доказательство теоремы Халин в сетке", Abhandlungen AUS DEM Mathematischen Семинаре дер Universität Hamburg , 74 : 237-242, DOI : 10.1007 / BF02941538 , MR 2112834.
- Дистель, Рейнхард; Кюн, Даниэла (2003), «Теоретико-графические и топологические концы графов», Журнал комбинаторной теории , серия B, 87 (1): 197–206, DOI : 10.1016 / S0095-8956 (02) 00034-5 , MR 1967888.
- Халин, Рудольф (1964), "Убер unendliche Wege в графене", Mathematische Annalen , 157 : 125-137, DOI : 10.1007 / bf01362670 , ЛВП : 10338.dmlcz / 102294 , МР 0170340.
- Халин, Рудольф (1965), "Убер умереть Maximalzahl fremder unendlicher Wege в графена", Mathematische Nachrichten , 30 : 63-85, DOI : 10.1002 / mana.19650300106 , МР 0190031.
- Сеймур, Пол Д .; Томас, Робин (1993), «Поиск в графах и теорема о минимуме и максимуме для ширины дерева», Журнал комбинаторной теории , серия B, 58 (1): 22–33, DOI : 10.1006 / jctb.1993.1027.