Теорема Халина о сетке

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

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

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

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

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

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

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

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

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

Ссылки

• Демейн, Эрик Д .; Хаджиагайи, Мохаммад Таги (2005), «Двумерность: новые связи между алгоритмами FPT и PTAS», Труды 16-го симпозиума ACM-SIAM по дискретным алгоритмам (SODA) (PDF) , стр. 590–601, MR   2298309 .
• Дистель, Рейнхард (2004), «Краткое доказательство теоремы Халина о сетке», статьи Математического семинара Гамбургского университета , 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), «О бесконечных путях в графах», Mathematical Annals , 157 : 125–137, doi : 10.1007/bf01362670 , hdl : 10338.dmlcz/102294 , MR   0170340 .
• Халин, Рудольф (1965), «О максимальном количестве странных бесконечных путей в графах», Mathematical News , 30 : 63–85, doi : 10.1002/mana.19650300106 , MR   0190031 .
• Сеймур, Пол Д .; Томас, Робин (1993), «Поиск по графу и теорема о мин-максе для ширины дерева», Журнал комбинаторной теории , серия B, 58 (1): 22–33, doi : 10.1006/jctb.1993.1027 .