Русская Википедия:Теорема Курселя

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в Шаблон:Не переведено 5 Шаблон:Не переведено 5, может быть установлено за линейное время на графах с ограниченной древесной ширинойШаблон:SfnШаблон:SfnШаблон:Sfn. Результат впервые доказан Шаблон:Не переведено 5 в 1990 годуШаблон:Sfn и независимо переоткрыт Бори, Паркером и ТовейемШаблон:Sfn. Результат считается прототипом алгоритмических метатеоремШаблон:SfnШаблон:Sfn.

Формулировки

Множества вершин

В варианте логики графов второго порядка, известном как MSO1[1], граф описывается множеством вершин V и бинарным отношением смежности adj(.,.), а ограничение логикой второго порядка означает, что свойство графа может быть определено в терминах множеств вершин заданного графа, но не в терминах множеств рёбер или пар вершин.

В качестве примера свойство графа раскрашиваемости в три цвета (представленный тремя множествами вершин R, G и B) может быть определён формулой логики второго порядка

∃R,G,B. (∀v∈V. (v∈R ∨ v∈G ∨ v∈B)) ∧
(∀u,v∈V. ((u∈R ∧ v∈R) ∨ (u∈G ∧ v∈G) ∨ (u∈B ∧ v∈B)) → ¬adj(u,v)).

Первая часть этой формулы обеспечивает, что три класса цветов включают все вершины графа, а вторая часть обеспечивает, что каждое из них образует независимое множество. (Можно также добавить предложение в формулу, обеспечивающее непересечение трёх классов цвета, но на результат это не повлияет.) Таким образом, по теореме Курселя можно проверить раскрашиваемость в 3 цвета графа с ограниченной древесной шириной за линейное время.

Для этого варианта логики графов теорема Курселя может быть расширена от древесной ширины до кликовой ширины — для любого фиксированного MSO1 свойства P и любой фиксированной границы b на кликовую ширину графа существует алгоритм линейного времени проверки, имеет ли граф с кликовой шириной, не превосходящей b, свойство PШаблон:Sfn.

Множества рёбер

Теорему Курселя можно использовать с более строгим вариантом логики графов второго порядка, известном как MSO2. В этой формулировке граф представляется множеством вершин V, множеством рёбер E и отношением инцидентности между вершинами и рёбрами. Этот вариант позволяет ввести количественный показатель над множеством вершин или рёбер, но не над более сложными отношениями над парами вершин и рёбер.

Например, свойство иметь гамильтонов цикл может быть выражено в MSO2 при определении цикла как множества рёбер, включающего ровно по два ребра, инцидентных каждой вершине, такого, что любое непустое собственное подмножество вершин имеет ребро в цикле и это ребро имеет в точности одну конечную точку в подмножестве. Гамильтоновость, однако, нельзя выразить в терминах MSO1Шаблон:Sfn.

Модульная сравнимость

Другое направление расширения теоремы Курселя касается логических формул, включающих предикаты для подсчёта длины теста. В этом контексте невозможно осуществить произвольные арифметические операции над размерами множеств, и даже невозможно проверить, что множества имеют один и тот же размер. Однако MSO1 и MSO2 могут быть расширены до логик, называемых CMSO1 и CMSO2, которые включают для любых двух констант q и r предикат <math>\operatorname{card}_{q,r}(S)</math>, который проверяет, сравнима ли мощность множества S с r по модулю q. Теорему Курселя можно расширить на эти логикиШаблон:Sfn.

Разрешимость и оптимизация

Как утверждалось выше, теорема Курселя применима, в основном, к задачам разрешимости — имеет граф свойство или нет. Те же методы, тем не менее, позволяют также решить задачи оптимизации, в которых вершинам или рёбрам графа присвоены некоторые целые веса и ищется минимум или максимум весов, для которых множество удовлетворяет заданному свойству, выраженному в терминах логики второго порядка. Эти задачи оптимизации могут быть решены за линейное время на графах с ограниченной кликовой ширинойШаблон:SfnШаблон:Sfn.

Ёмкостная сложность

Вместо ограничения временной сложности алгоритма, распознающего MSO-свойства графов с ограниченной древесной шириной, можно также анализировать Шаблон:Не переведено 5 таких алгоритмов, то есть величину памяти, необходимую сверх входных данных (в предположении, что входные данные не могут быть изменены и занятая под них память не может быть использована в других целях). В частности, можно распознать графы с ограниченной древесной шириной и любое MSO-свойство на этих графах с помощью детерминированной машины Тьюринга, которая использует только Шаблон:Не переведено 5Шаблон:Sfn.

Стратегия доказательства и сложность

Типичный подход к доказательству теоремы Курселя использует построение конечного восходящего Шаблон:Не переведено 5, действующего на древесных декомпозициях данного графаШаблон:Sfn.

Более подробно, два графа G1 и G2, каждый с указанным подмножеством T вершин, называемых конечными, могут считаться эквивалентными согласно MSO-формуле F, если для любого другого графа H, пересечение которого с G1 и G2 состоит только из вершин T, два графа G1 ∪ H и G2 ∪ H ведут себя одинаково по отношению к формуле F — либо оба удовлетворяют F, либо оба не удовлетворяют F. Это отношение эквивалентности, и по индукции по длине F можно показать (если размеры T и F ограничены), что отношение имеет конечное число классов эквивалентностиШаблон:Sfn.

Древесная декомпозиция заданного графа G состоит из дерева и, для каждого узла дерева, подмножества вершин графа G, называемого корзиной. Это подмножество должно удовлетворять двум свойствам — для каждой вершины v из G корзина, содержащая v, должна быть ассоциирована с неразрывным поддеревом и для каждого ребра uv из G должна существовать корзина, содержащая как u, так и v. Вершины в корзине могут пониматься как конечные элементы подграфа G, представленные поддеревьями древесной декомпозиции, растущими из этой корзины. Если граф G имеет ограниченную древесную ширину, он имеет древесную декомпозицию, в которой все корзины имеют ограниченный размер и такое разложение может быть найдено за фиксированно-параметрически разрешимое времяШаблон:Sfn. Более того, можно выбрать древесное разложение, образующее двоичное дерево с только двумя дочерними поддеревьями на корзину. Таким образом, можно осуществить восходящее вычисление на этой древесной декомпозиции, вычисляя идентификатор для класса эквивалентности поддерева, имеющего корень в каждой корзине, путём комбинирования рёбер, представленных внутри корзины, с двумя идентификаторами классов эквивалентности двух дочерних элементовШаблон:Sfn.

Размер автомата, построенного таким способом, не является элементарной функцией от размера входной MSO-формулы. Эта неэлементарная сложность приводит к тому, что невозможно (если только не P = NP) проверить MSO-свойства за время, фиксированно-параметрически разрешимое с элементарной функциональной зависимостью от параметраШаблон:Sfn.

Гипотеза Курселя

Доказательство теоремы Курселя показывает более строгий результат — не только любое (с предикатом подсчёта длины) свойство логики второго порядка может быть распознано за линейное время для графов с ограниченной древесной шириной, но и оно может быть распознано конечным Шаблон:Не переведено 5. Гипотеза Курселя обратна этому — если свойство графов с ограниченной шириной распознаётся автоматом над деревьями, то оно может быть определено в терминах логики второго порядка. Несмотря на попытки доказательства, предпринятые ЛапуаромШаблон:Sfn, гипотеза считается недоказаннойШаблон:Sfn. Однако известны некоторые специальные случаи, в частности, гипотеза верна для графов с древесной шириной три и менееШаблон:Sfn.

Более того, для графов Халина (специального вида графов с древесной шириной три) предикат подсчёта длины не обязателен — для этих графов любое свойство, которое может быть распознано автоматом на деревьях, может быть определено в терминах логики второго порядка. То же самое верно, в более общем случае, для некоторых классов графов, в которых древесная декомпозиция сама может быть описана в MSOL. Однако это не может быть верно для всех графов с ограниченной древесной шириной, поскольку, в общем случае, предикат подсчёта длины добавляет силу логике второго порядка. Например, графы с чётным числом вершин могут быть распознаны по предикату, но не могут быть распознаны без негоШаблон:Sfn.

Выполнимость и теорема Сииза

Шаблон:Не переведено 5 для формул логики второго порядка является задачей определения, существует ли по меньшей мере один граф (возможно, принадлежащий ограниченному семейству графов), для которого формула верна. Для произвольных семейств графов и произвольных формул эта задача неразрешима. Выполнимость формул MSO2, однако, разрешима для графов с ограниченной древесной шириной, а выполнимость формул MSO1 разрешима для графов с ограниченной кликовой шириной. Доказательство использует построение автомата над деревом для формулы, а затем проверку, имеет ли автомат приемлемый путь.

В качестве частично обратного утверждения СиизШаблон:Sfn доказал, что всякий раз, когда семейство графов имеет разрешимую проблему MSO2 выполнимости, семейство должно иметь ограниченную древесную ширину. Доказательство опирается на теорему Робертсона и Сеймура о том, что семейства графов с неограниченной древесной шириной имеют произвольно большие миноры-решёткиШаблон:Sfn. Сииз также высказал предположение, что любое семейство графов с разрешимой проблемой MSO1 выполнимости должно иметь ограниченную кликовую ширину. Гипотеза не доказана, но ослабленная гипотеза с заменой MSO1 на CMSO1 вернаШаблон:Sfn.

Приложения

ГроэШаблон:Sfn использовал теорему Курселя, чтобы показать, что вычисление числа пересечений графа G является Шаблон:Не переведено 5 задачей с квадратичной зависимостью от размера G, что улучшает кубический по времени алгоритм, основанный на теореме Робертсона — Сеймура. Более позднее улучшение до линейного времени Каварабайаши и РиидомШаблон:Sfn использует тот же подход. Если данный граф G имеет малую древесную ширину, теорема Курселя может быть применена к этой проблеме непосредственно. С другой стороны, если G имеет большую древесную ширину, то он содержит большой минор-решётку, внутри которого граф может быть упрощён без изменения числа пересечений. Алгоритм Гроэ осуществляет это упрощение, пока оставшийся граф не будет иметь малую древесную ширину, а затем применяет теорему Курселя для решения уменьшенной подзадачиШаблон:SfnШаблон:Sfn.

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

В вычислительной топологии Бартон и ДауниШаблон:Sfn расширили теорему Курселя с MSO2 до логики второго порядка на симплициальных комплексах ограниченной размерности, что позволяет введение количественных характеристик для любой фиксированной размерности. Как следствие, они показали, как вычислить некоторые Шаблон:Не переведено 5 3-многообразий, а также как решить эффективно некоторые задачи в Шаблон:Не переведено 5, когда многообразие имеет триангуляцию (исключая вырожденные симплексы), двойственный граф которой имеет малую древесную ширинуШаблон:Sfn.

Методы, основанные на теореме Курселя, были использованы в Шаблон:Не переведено 5Шаблон:Sfn, представлении знаний и логических выводовШаблон:Sfn, теории автоматовШаблон:Sfn и проверке моделейШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ MSO = monadic second-order
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Теорема_Курселя&oldid=10919767