WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути[1], а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит (хотя бы) одному из множеств[2], а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции. Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число[3][4].

Путевая ширина и путевая декомпозиция являются тесной аналогией с древесной шириной и древесной декомпозицией. Они играют ключевую роль в теории миноров графа — семейства графов, замкнутых относительно миноров графа и не включающих все леса могут быть охарактеризованы как имеющие ограниченную путевую ширину[2], и «вихри», возникающие в общей структурной теорией семейств графов, замкнутых по минорам, имеют ограниченную путевую ширину[5]. Путевая ширина и графы с ограниченной путевой шириной имеют приложение в разработке СБИС, визуализации графов и компьютерной лингвистике.

Задача нахождения путевой ширины произвольных графов является NP-трудной. Более того, NP-трудна даже задача аппроксимации путевой ширины точно[6][7]. Однако эта задача является фиксированно-параметрически разрешимой — проверка, имеет ли граф путевую ширину k, может быть решена за время, которое линейно зависит от размера графа, но суперэкспоненциально от k[8] Кроме того, для некоторых специальных классов графов, таких как деревья, путевая ширина может быть вычислена за полиномиальное время, независимое от k[9][10]. Многие задачи теории графов можно эффективно решить на графах с ограниченной путевой шириной при помощи динамического программирования на путевой декомпозиции графа[11]. Древесную декомпозицию можно также использовать для оценки ёмкостной сложности[en] алгоритмов динамического программирования на графах с ограниченной древесной шириной[12].

Определение

Пример графа G с путевой шириной 2 и его путевая декомпозиция ширины 2. В нижней части рисунка приведён тот же граф и путевая декомпозиция с добавленными цветами для выразительности. (Этот пример взят из книги Бодлаендера[13], и добавлены цвета)

В первой знаменитой серии статей о минорах минорах графа Робертсон и Сеймур[2] определили путевую декомпозицию графа G как последовательность подмножеств Xi вершин графа G с двумя свойствами:

  1. Для каждого ребра G, существует i, такого, что обе конечные точки ребра принадлежат подмножеству Xi
  2. Для любых трёх индексов i ≤ j ≤ k, Xi ∩ Xk ⊆ Xj.

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

Ширина путевой декомпозиции определяется тем же способом, что и для древесной декомпозиции, как maxi |Xi| − 1, а путевая ширина графа G равна минимальной ширине всех путевых декомпозиций графа G. Вычитание единицы из размера Xi в этом определении мало влияет на большинство приложений путевой ширины, но зато делает путевую ширину пути равной единице.

Альтернативные описания

Как пишет Бодлаендер[3], путевая ширина может быть описана многими эквивалентными способами.

Склеивание последовательностей

Древесную декомпозицию можно описать как последовательность графов Gi, которые склеены путём отождествления пар вершин в соседних графах последовательности, и в результате этого склеивания образуется граф G. В качестве графов Gi можно взять порождённые подграфы множеств Xi в первом определении путевой декомпозиции, со склеиванием вершин в соседних порождённых подграфах, если эти вершины порождены той же самой вершиной из G. В другом направлении можно взять Xi в качестве множеств вершин графов Gi. Ширина древесной декомпозиции тогда на единицу меньше максимального числа вершин в одном из графов Gi[2].

Интервальная толщина

Интервальный граф с путевой шириной два, на единицу меньшей числа четырёх максимальных клик ABC, ACD, CDE и CDF.

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

В одном направлении, предположим, что древесная декомпозиция графа G задана. Тогда можно представить вершины декомпозиции как точки на прямой (в том порядке, в котором они входят в путь) и представить каждую вершину v как замкнутый интервал, имеющий эти точки в качестве конечных точек. Например, пусть (X1, . . . , Xr) — путевая декомпозиция графа G, точки на прямой — [1, . . . , r], тогда представление вершины v — это интервал . Тогда древесная декомпозиция вершин, содержащих v, соответствует представляющим (т.е. конечным точкам) интервала для v. Граф пересечений интервалов, образованный из вершин G — это интервальный граф, содержащий G в качестве подграфа. Его максимальные клики задаются множеством интервалов, содержащих представляющие точки, и их размер наибольшей клики на единицу больше путевой ширины графа G.

В другом направлении, если G — подграф интервального графа с кликовым числом p + 1, то граф G имеет древесную декомпозицию ширины p, вершины которой заданы максимальными кликами интервального графа. Например, интервальный граф, показанный с его интервальным представлением на рисунке, имеет древесную декомпозицию с пятью вершинами, соответствующими пяти максимальным кликам ABC, ACD, CDE, CDF и FG. Размер максимальной клики равен трём, а ширина этой древесной декомпозиции равна двум.

Эта эквивалентность между путевой шириной и интервальной толщиной является тесной аналогией с эквивалентностью между древесной шириной и минимальным кликовым числом (минус единица) хордального графа, для которого данный граф является подграфом. Интервальные графы являются специальным случаем хордальных графов, а хордальные графы можно представить в виде графов пересечений поддеревьев общих деревьев, что обобщает подход, при котором интервальные графы интерпретируются как графы пересечений подпутей пути.

Величина вершинного разделения

Предположим, что вершины графа G линейно упорядочены. Тогда величина вершинного разделения графа G — это наименьшее число s, такое, что для каждой вершины v максимум s вершин предшествуют v в упорядочении, которые имеют v или одну из следующих за ней вершин в окрестности. Величина вершинного разделения графа G — это минимальная величина вершинного разделения любого линейного любого линейного упорядочения графа G. Величину вершинного разделения ввели Эллис, Садбороу и Тёрнер[15] и она равна путевой ширине графа G[16][17]. Это следует из ранее упомянутой эквивалентности интервальных графов и кликовых чисел — если G является подграфом интервального графа I, представленного (как на рисунке) таким образом, что все концы интервалов различны, то порядок левых концов интервалов графа I имеют величину вершинного разделения на единицу меньше кликового числа графа I. В другом направлении, из линейного упорядочения графа G можно получить интервальное представление, в котором левая конечная точка интервала для вершины v является позицией в упорядочении, а правая конечная точка является позицией соседа v, который в упорядочении последний.

Вершинно-поисковое число

Игра «поиск вершины» на графе — это вид игры преследования-уклонения[en], в которой множество преследователей совместно пытаются выследить беглеца, спрятавшегося в графе. Преследователи размещаются в вершинах графа, в то время как беглец может находиться на любом ребре графа, его местоположение и ходы преследователям не видны. Во время очередного хода некоторые (или все) преследователи могут перейти (произвольным образом, не обязательно вдоль рёбер) из одной вершины в другую, а беглец движется затем вдоль любого пути на графе, но не может проходить через занятые преследователями вершины. Беглец пойман, когда оба конца дуги, на которой он находится, заняты преследователями. Вершинно-поисковое число графа — это минимальное число преследователей, необходимых для гарантированной поимки беглеца вне зависимости от его поведения. Как показали Кироузис и Панадимитриу[18], вершинно-поисковое число графа равно его интервальной толщине. Оптимальной стратегией для преследователей служат ходы, в которых преследователи последовательно образуют разделяющие множества линейного упорядочивания с минимальной величиной вершинного разделения.

Границы

Граф-гусеница, максимальный граф с путевой шириной один.

Любой граф с n вершинами и путевой шириной k имеет максимум k(n − k + (k − 1)/2)) рёбер, и максимальные графы с путевой шириной k (графы, к которым нельзя добавить ребро без увеличения путевой ширины) имеют в точности это число рёбер. Максимальный граф с путевой шириной k должен быть либо k-путём, либо k-гусеницей, т.е. одного из двух специальных видов k-дерева. k-дерево — это хордальный граф с в точности n − k максимальными кликами, каждая из которых содержит k + 1 вершин. В k-дереве, которое не является само по себе (k + 1)-кликой, каждая максимальная клика либо делит граф на две или более компоненты, либо содержит единичную листовую вершину, вершину, которая принадлежит только одной максимальной клике. k-путь — это k-дерево с максимум двумя листьями, а k-гусеница — это k-дерево, которую можно разбить на k-путь и множество k-листов, каждый из которых смежен с сепаратором k-клики k-пути. В частности, максимальные графы путевой ширины единица — это в точности графы-гусеницы [19].

Поскольку путевые декомпозиции являются специальными случаями древесных декомпозиций, путевая ширина любого графа больше либо равна его древесной ширине. Путевая ширина также меньше или равна ширине разреза, минимального числа рёбер, пересекающих любое сечение между вершинами с меньшим индексом и большим индексом в оптимальном линейном упорядочении вершин графа. Это следует из факта, что величина вершинного разделения, число вершин с меньшим индексом с соседами, имеющими больший индекс, не больше числа разрезающих рёбер[20][21]. По такой же причине ширина разреза не превосходит путевой ширины, умноженной на максимальную степень вершин в данном графе[22][23].

Любой лес с n вершинами имеет путевую ширину O(log n)[24][25][26]. Для леса можно всегда найти постоянное число вершин, удаление которых приводит к лесу, который можно разбить на два меньших леса с максимум 2n/3 вершин в каждом из этих лесов. Линейное упорядочение, образованное рекурсивным применением такого разбиения, имеет логарифмическое поисковое число для вершин. Та же техника, применённая к древесной декомпозиции графа, показывает, что если древесная ширина графа G с n вершинами равна t, то путевая ширина графа G равна O(t log n)[27][28]. Поскольку внешнепланарные графы, параллельно-последовательные графы и графы Халина все имеют ограниченную древесную ширину, все они имеют максимум логарифмическую путевую ширину.

Кроме того, что путевая ширина связана с древесной шириной, она связана с кликовой шириной и шириной разреза через рёберные графы. Рёберный граф L(G) графа G имеет вершину для каждого ребра графа G и две вершины в L(G) смежны, если соответствующие два ребра имеют G общие конечные точки. Любое семейство графов имеет ограниченную путевую ширину тогда и только тогда, когда его рёберные графы имеют ограниченную линейную кликовую ширину, где линейная кликовая ширина заменяет операцию объединения в определении кликовой ширины на операцию присоединения отдельной новой вершины[29]. Если связный граф с тремя или более вершинами имеет максимальную стпепень 3, его ширина разреза равна величине вершинного разделения его рёберного графа[30].

В любом планарном графе путевая ширина в худшем случае пропорциональна квадратному корню от числа вершин[31]. Один из способов поиска путевой декомпозиции с такой шириной — (подобно путевой декомпозиции с логарифмической шириной лесов, описанной выше) использовать теорему о планарном разбиении, чтобы найти множество из O(√n) вершин, удаление которых разбивает граф на два подграфа с максимум 2n/3 вершинами в каждом, и соединить рекурсивно построенные для этих двух подграфов путевые декомпозиции. Та же техника применима к любому классу графов, для которых выполняется подобная теорема о разбиении[32]. Поскольку любое семейство графов, замкнутое относительно взятия миноров, как и в случае планарных графов, имеет разбивающее множество вершин размера O(√n)[33], отсюда следует, что путевая ширина графов в любом фиксированном замкнутом относительно миноров семействе снова равна O(√n). Для некоторых классов планарных графов путевая ширина графа и путевая ширина его двойственного графа должны лежать в интервале, границы которого линейно зависят от значений — такие границы известны для двусвязных внешнепланарных графов[34][35] и для графов многогранников[36][37]. Для двусвязных планарных графов путевая ширина двойственного графа меньше, чем путевая ширина рёберного графа[38]. Остаётся открытым вопрос, являются ли путевые ширины планарного графа и его двойственного всегда в линейных границах для остальных случаев.

Для некоторых классов графов доказано, что путевая ширина и древесная ширина всегда равны друг другу — это верно для кографов[39], графов перестановки [40], дополнений графов сравнимости[41] и графов сравнимости интервальных порядков[en][42].

Нерешённые проблемы математики: Какова максимальная путевая ширина кубического графа с вершинами?

В любом кубическом графе, или, более обще, любом графе с максимальной степенью вершин 3, путевая ширина не превосходит n/6 + o(n), где n — число вершин графа. Существуют кубические графы с путевой шириной 0.082n, но неизвестно, как сократить этот разрыв между нижней границей[en] и верхней границей n/6[43].

Вычисление путевых декомпозиций

Определение, не превосходит ли путевая ширина заданное значение k для заданного графа, является NP-полной задачей, если k является входным параметром [6]. Наиболее известные временные границы (в худшем случае[en]) вычисления путевой ширины произвольного графа с n вершинами имеют вид O(2n nc) при некоторой константе c[44]. Тем не менее, известны некоторые алгоритмы вычисления путевой декомпозиции с большей эффективностью, если путевая ширина мала, если класс входных графов ограничен, или требуется вычислить путевую ширину приближённо.

Фиксированно-параметрически разрешимость

Путевая ширина фиксированно-параметрически разрешима[en] — для любой постоянной k можно проверить, не превосходит ли путевая ширина величину k, и если не превосходит, найти путевую декомпозицию ширины k за линейное время [8]. В целом, эти алгоритмы работают в два этапа. На первом этапе используется предположение, что граф имеет путевую ширину k, для поиска путевой декомпозиции или древесной декомпозиции. Эта декомпозиция не оптимальна, но её ширина может быть ограничена функцией от k. На втором этапе применяется алгоритм динамического программирования для поиска оптимальной декомпозиции. Однако временные границы для известных алгоритмов этого типа экспоненциальны от k2 и не представляют практического интереса, разве что для малых значений k[45]. Для случая k = 2 Фляйтер дал алгоритм с линейным временем работы, основанный на структурной декомпозиции графов с путевой шириной 2 [46].

Специальные классы графов

Бодлаендер [9] дал обозрение сложности задач вычисления путевой ширины на различных специальных классах графов. Определение, превосходит ли путевая ширина графа G величину k, остаётся NP-полной задачей, если G берётся из графов ограниченной степени[47], планарные графы[47], планарных графов ограниченной степени[47], хордальных графов[48], хордальных домино[49], дополнений графов сравнимости[41], и двудольных дистанционно-наследуемых графов[50]. Отсюда немедленно следует, что задача также NP-полна для семейств графов, содержащих двудольные дистанционно-наследуемые графы, включая двудольные графы, хордальные двудольные графы дистанционно-наследуемые графы и круговые графы[50].

Однако путевую ширину можно вычислить за линейное время для деревьев и лесов [10]. Можно вычислить эту величину за полиномиальное время для графов ограниченной древесной ширины, в которые входят параллельно-последовательные графы, внешнепланарные графы и графы Халина [8], а также расщепляемые графы[51][48], дополнения хордальных графов [52], графы перестановки[40], кографы[39], графы дуг окружности[53], графы сравнимости интервальных порядков[42], и, конечно, сами интервальные графы, поскольку для них путевая ширина просто на единицу меньше максимального числа интервального накрытия любой точки в интервальном представлении графа.

Аппроксимационные алгоритмы

NP-трудной задачей является аппроксимация путевой ширины графа аддитивной константой[7]. Лучший известный аппроксимационный коэффициент аппроксимационных алгоритмов полиномиального времени для путевой ширины равен O((log n)3/2)[54]. Ранние аппроксимационные алгоритмы для путевой ширины можно найти у Бодлаендера, Гилберта, Хафштейнссона, Клокса[7] и Гуха[55]. Для аппроксимации ограниченных классов графов см. книгу Клокса и Бодлаендера[51].

Миноры графа

Минор графа G — это другой граф, образованный из G путём стягивания рёбер, удаления рёбер и вершин. Миноры графа имеют глубокую теорию, в которой некоторые некоторые важные результаты используют путевую ширину.

Исключение леса

Если семейство F графов замкнуто по отношению к операции взятия миноров (любой минор члена семейства F также содержится в F), тогда по теореме Робертсона – Сеймура семейство F можно охарактеризовать как графы, не содержащие миноров из X, где X — конечное множество запрещённых миноров [56]. Например, теорема Вагнера утверждает, что планарные графы — это графы, которые не содержат ни полного графа K5, ни полного двудольного графа K3,3 в качестве миноров. Во многих случаях свойства F и свойства X тесно связаны, и первый результат такого типа получили Робертсон и Сеймур [2] и он связывает существование ограниченной путевой ширины с наличием леса в семействе запрещённых миноров. Конкретнее, определим семейство F графов как имеющее ограниченную путевую ширину, если существует константа p, такая, что любой граф из F имеет путевую ширину, не превосходящую p. Тогда минорно-замкнутое семейство F имеет ограниченную путевую ширину тогда и только тогда, когда множество X запрещённых миноров для F включает хотя бы один лес.

В одном направлении этот результат можно доказать прямо — а именно, что если X не содержит хотя бы один лес, то свободные от X-миноров графы не имеет ограниченной путевой ширины. В этом случае свободные от X-миноров графы включают все леса, и, в частности, совершенные бинарные деревья. Но совершенные бинарные деревья с 2k + 1 уровнями имеют путевую ширину k, так что в этом случае свободные от X-миноров графы имеют неограниченную путевую ширину. В обратном направлении, если X содержит лес с n вершинами, то свободные от X-миноров графы имеют путевую ширину, не превосходящую n − 2[57][58][59].

Оценки путевой ширины

Запрещённые миноры для графов с путевой шириной 1.

Свойство иметь путевую ширину не больше p является, само по себе, замкнутым по взятию миноров свойством — если G имеет путевую декомпозицию с шириной, не превосходящей p, то та же самая путевая декомпозиция остаётся верной, если удалить любое ребро из G, а также любая вершина может быть удалена из графа G и его путевой декомпозиции без увеличения ширины. Стягивание ребра также может быть завершено без увеличения ширины декомпозиции путём слияния подпутей, представляющих два конца стягиваемого ребра. Таким образом, графы с путевой шириной, не превосходящей p, могут быть охарактеризованы множеством Xp запрещённых миноров[56][16][60][61].

Хотя Xp обязательно включает по меньшей мере один лес, неверно, что все графы в Xp являются лесами. Например, X1 состоит из двух графов, дерева с семью вершинами и треугольника K3. Однако множество деревьев в Xp можно точно описать — это в точности те деревья, которые можно образовать из трёх деревьев из Xp − 1 путём образования нового корня и соединения его рёбрами с произвольно выбранными вершинами меньших деревьев. Например, дерево с семью вершинами в X1 образовано из деревьев с двумя вершинами (одно ребро) из X0. Основываясь на этом построении, можно показать, что число запрещённых миноров в Xp не меньше (p!)2[16][60][61]. Полное множество X2 запрещённых миноров для графов с путевой шириной 2 вычислено. Это множество содержит 110 различных графов[62].

Структурная теория

Структурная теорема графов для семейств замкнутых по минорам графов утверждает, что для любого семейства F, в котором графы могут быть разложены на cуммы по клике графов, которые могут быть вложены в поверхности ограниченного рода вместе с ограниченным числом верхушек и вихрей для каждой компоненты суммы по клике. Верхушка — это вершина, которая смежна со всеми вершинами компоненты, а вихрь — это граф ограниченной путевой ширины, который приклеивается к грани компоненты с вложением ограниченного рода. Циклический порядок вершин вокруг грани, в которую вихрь вложен, должен быть совместим с древесной декомпозицией вихря в том смысле, что разрыв цикла для образования линейного упорядочения должен привести к упорядочению с ограниченной величиной вершинного разделения[5]. Эта теория, в которой путевая ширина тесно связана с произвольными семействами графов, замкнутых относительно миноров, имеет важное алгоритмическое применение[63].

Приложения

СБИС

При разработке СБИС задача разделения вершин первоначально изучалась как путь разделения цепей на меньшие подсистемы с малым числом компонент на границе между системами[47].

Отцуки, Мори, Кух и Кашивабара[64] использовали интервальную толщину для моделирования числа проводников, необходимых в одномерном расположении цепей СБИС, образованных множеством модулей, которые необходимо соединить системой сетей. В их модели можно образовать граф, в котором вершины представляют цепи и в которой две вершины соединены ребром, если их цепи соединены к одному и тому же модулю. То есть если модули и цепи понимаются как вершины и гиперрёбра гиперграфа, то граф, образованный из них, является рёберным графом гиперграфа. Интервальное представление суперграфа этого рёберного графа вместе с раскраской суперграфа описывает расположение цепей вдоль горизонтальных дорожек (одна дорожка на каждый цвет), так что модули могут быть расположены вдоль дорожек в линейном порядке и соединены с нужными цепями. Из факта, что интервальные графы являются совершенными[65], следует, что число цветов, необходимых для оптимальной раскладки такого типа, равно кликовому числу интервального дoполнения графа цепей.

Матричная укладка переключателей[66] является специфическим видом КМОП СБИС укладки для цепей алгебры логики. В матричных укладках переключателей сигнал распространяется вдоль "линий" (вертикальных отрезков), в то время как каждый переключатель образуется последовательностью элементов, располагающихся на горизонтальном отрезке. Таким образом, горизонтальные отрезки для каждого переключателя должны пересекать вертикальные отрезки для каждой линии, которая служит входом или выходом переключателя. Как и в укладках Отцуки, Мори, Куха и Кашивабара[64] укладка такого типа, минимизирующая число вертикальных прямых, может быть вычислена путём вычисления путевой ширины графа, имеющего прямые в качестве вершин, а пары прямых, принадлежащих переключателю, в качестве рёбер[67]. Тот же алгоритмический подход может быть также использован для моделирования задач укладки в программируемых логических интегральных схемах[en][68][69].

Визуализация графов

Путевая ширина имеет несколько приложений для визуализации графов:

  • Минимальные графы, имеющие заданное число пересечений, имеют путевую ширину, ограниченную функцией от числа пересечений[70].
  • Число параллельных прямых, на которых можно расположить вершины дерева без пересечения рёбер (при различных естественных ограничениях на способы, которыми смежные вершины могут быть помещены на прямых с учётом последовательности прямых) пропорционально путевой ширине дерева[71].
  • k-пересечённый h-уровневый рисунок графа G — это расположение вершин графа G на h различных горизонтальных прямых с рёбрами в виде монотонных (представленных ломаными) путей между прямыми, в котором имеется не более k пересечений. Графы с таким представлением имеют путевую ширину, ограниченную функцией от h и k. Таким образом, если величины h и k постоянны, можно за линейное время определить, имеется ли у графа k-пересечённый h-уровневый рисунок[72].
  • Граф с n вершинами и путевой шириной p может быть вложен в трёхмерную решётку размера p × p × n таким образом, что никакие два ребра (представленные прямолинейными отрезками между точками решётки) не пересекают друг друга. Таким образом, графы ограниченной путевой ширины имеют вложения этого типа с линейным объёмом[73].

Проектирование компиляторов

При трансляции высокоуровневых языков программирования путевая ширина возникает в задаче переупорядочения линейного кода (то есть кода без управляющей логики — переходов и циклов) таким образом, что все значения, вычисленные в коде, могут быть в машинные регистры, а не вытеснены в основную память. В этом приложении оттранслированный код представляется в виде направленного ациклического графа (НАГ), в котором вершины представляют входные значения для кода и значения, вычисленные в результате операций внутри кода. Ребро из вершины x в вершину y в этом НАГ представляет факт, что значение x является одним из входных параметров для операции y. Топологическая сортировка вершин в этом НАГ представляет правильную сортировку кода, а число регистров, нужных для выполнения кода в этом порядке задаётся величиной вершинного разделения упорядочения[74].

Для любого фиксированного числа w регистров в машине можно определить за линейное время, может ли фрагмент линейного кода быть переупорядочен так, что для кода потребуется максимум w регистров. Если величина вершинного разделения топологического упорядочения не превосходит w, минимальное вершинное разделение среди всех упорядочений не может быть больше, так что неориентированные графы, образованные игнорированием ориентации НАГ, описанного выше, должны иметь путевую ширину, не превосходящую w. Можно проверить, верно ли это с помощью известных фиксированно-параметрически разрешимых алгоритмов для путевой ширины, и если верно, найти путевую декомпозицию для неориентированных графов за линейное время в предположении, что w является константой. Как только древесная декомпозиция найдена, топологическое упорядочение с шириной w (если такое существует) может быть найдено с использованием динамического программирования, опять же за линейное время[74].

Лингвистика

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

Экспоненциальные алгоритмы

Многие задачи теории графов могут быть эффективно решены на графах с малой путевой шириной при помощи динамического программирования, опираясь на путевую декомпозицию графа[11]. Например, если линейное упорядочение вершин графа G с n вершинами задано и величина вершинного разделения равна w, то можно найти наибольшее независимое множество графа G за время O(2w n)[43]. На графе с ограниченной путевой шириной этот подход ведёт к фиксированно-параметрически разрешимым алгоритмам, параметризованным по путевой ширине[67]. Такие результаты не часто встречаются в литературе, поскольку они принадлежат группе похожих алгоритмов, параметризованных по древесной ширине. Однако путевая ширина появляется даже в алгоритмах динамического программирования, основанных на древесной ширине, при измерении ёмкостной сложности[en] этих алгоритмов[12].

Тот же самый метод динамического программирования может быть применён к графам с неограниченной путевой шириной, что приводит к алгоритмам, решающим непараметризованные задачи на графах за экспоненциальное время. Например, комбинация подхода динамического программирования с фактом, что кубические графы имеют путевую ширину n/6 + o(n), показывает, что для кубических графов максимальное независимое множество можно построить за время O(2n/6 + o(n)), что быстрее известных до этого методов[43]. Похожий подход ведёт к улучшенным алгоритмам экспоненциального времени для задач максимального разреза и минимального доминирующего множества для кубических графов[43] и для некоторых других NP-трудных оптимизационных задач[77][78].

См. также

  • Интервальная размерность графа, другой путь измерения сложности произвольных графов в терминах интервальных графов
  • Глубина дерева, число, которое ограничено для минорно-замкнутых семейств графов тогда и только тогда, если семейство не содержит пути
  • Вырождение[en], мера разреженности графа, которая не больше путевой ширины графа
  • Ширина ленты графа[en], другая NP-полная задача оптимизация, использующая линейные укладки графов
  • Число Стралера, мера плотности корневых деревьев, определяемое подобно путевой ширине неориентированных деревьев

Примечания

  1. ↑ Diestel, Kühn, 2005.
  2. 1 2 3 4 5 Robertson, Seymour, 1983.
  3. 1 2 Bodlaender, 1998.
  4. ↑ Множество используемых в статье терминов можно найти во введении в диссертацию Ф. В. Фомина ((Фомин 1996))
  5. 1 2 Robertson, Seymour, 2003.
  6. 1 2 Kashiwabara, Fujisawa, 1979; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979; Lengauer, 1981; Arnborg, Corneil, Proskurowski, 1987.
  7. 1 2 3 Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992.
  8. 1 2 3 Bodlaender (1996); Bodlaender, Kloks (1996)
  9. 1 2 Bodlaender, 1994.
  10. 1 2 Möhring, 1990; Scheffler, 1990; Ellis, Sudborough, Turner, 1994; Coudert, Huc, Mazauric, 1998; Peng, Ho, Hsu, Ko, Tang, 1998; Skodinis, 2000; Skodinis (2003).
  11. 1 2 Arnborg, 1985.
  12. 1 2 Aspvall, Proskurowski, Telle, 2000.
  13. ↑ Bodlaender, 1994, с. 1–2.
  14. ↑ Bodlaender, 1998, с. 13, Theorem 29.
  15. ↑ Ellis, Sudborough, Turner, 1983.
  16. 1 2 3 Kinnersley, 1992.
  17. ↑ Bodlaender, 1998, с. Theorem 51.
  18. ↑ Kirousis, Papadimitriou, 1985.
  19. ↑ Proskurowski, Telle, 1999.
  20. ↑ Korach, Solel, 1993, с. 99, Lemma 3.
  21. ↑ Bodlaender, 1998, с. 24, Theorem 47.
  22. ↑ Korach, Solel, 1993, с. 99, Lemma 1.
  23. ↑ Bodlaender, 1998, с. 24, Theorem 49.
  24. ↑ Korach, Solel, 1993, с. 99, Theorem 5.
  25. ↑ Bodlaender, 1998, с. 30, Theorem 66.
  26. ↑ Шеффлер (Scheffler (1992)) даёт более сильную границу log3(2n + 1) путевой ширины леса с n вершинами.
  27. ↑ Korach, Solel, 1993, с. 100, Theorem 6.
  28. ↑ Bodlaender, 1998, с. 10, Corollary 24.
  29. ↑ Gurski, Wanke, 2007.
  30. ↑ Golovach, 1993.
  31. ↑ Bodlaender, 1998, с. 10, Corollary 23.
  32. ↑ Bodlaender, 1998, с. 9, Theorem 20.
  33. ↑ Alon, Seymour, Thomas, 1990.
  34. ↑ Bodlaender, Fomin, 2002.
  35. ↑ Coudert, Huc, Sereni, 2007.
  36. ↑ Fomin, Thilikos, 2007.
  37. ↑ Amini, Huc, Pérennes, 2009.
  38. ↑ Fomin, 2003.
  39. 1 2 Bodlaender, Möhring, 1990.
  40. 1 2 Bodlaender, Kloks, Kratsch, 1993.
  41. 1 2 Habib, Möhring, 1994.
  42. 1 2 Garbe, 1995.
  43. 1 2 3 4 Fomin, Høie, 2006.
  44. ↑ Fomin, Kratsch, Todinca, Villanger, 2008.
  45. ↑ Downey, Fellows, 1999, с. 12.
  46. ↑ de Fluiter, 1997.
  47. 1 2 3 4 Monien, Sudborough, 1988.
  48. 1 2 Gusted, 1993.
  49. ↑ Kloks, Kratsch, Müller, 1995. Хордальное домино — это хордальный граф, в котором любая вершина принадлежит максимум двум максимальным кликам
  50. 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993.
  51. 1 2 Kloks, Bodlaender, 1992.
  52. ↑ Гарбе (Garbe (1995)) приписывает этот результат тезисам диссертации Тона Клокса 1993 года. Алгоритм полиномиального времени Гарбе для графов сравнимости интервальных упорядочений обобщает этот результат, поскольку любой хордальный граф должен быть графом сравнимости такого типа.
  53. ↑ Suchan, Todinca, 2007.
  54. ↑ Feige, Hajiaghayi, Lee, 2005.
  55. ↑ Guha, 2000.
  56. 1 2 Robertson, Seymour, 2004.
  57. ↑ Bienstock, Robertson, Seymour, Thomas, 1991.
  58. ↑ Diestel, 1995.
  59. ↑ Cattell, Dinneen, Fellows, 1996.
  60. 1 2 Takahashi, Ueno, Kajitani, 1994.
  61. 1 2 Bodlaender, 1998, с. 8.
  62. ↑ Kinnersley, Langston, 1994.
  63. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2005.
  64. 1 2 Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979.
  65. ↑ Berge, 1967.
  66. ↑ Lopez, Law, 1980.
  67. 1 2 Fellows, Langston, 1989.
  68. ↑ Möhring, 1990.
  69. ↑ Ferreira, Song, 1992.
  70. ↑ Hliněny, 2003.
  71. ↑ Suderman, 2004.
  72. ↑ Dujmović, Fellows, Kitching и др., 2008.
  73. ↑ Dujmović, Morin, Wood, 2003.
  74. 1 2 Bodlaender, Gustedt, Telle, 1998.
  75. ↑ Kornai, Tuza, 1992.
  76. ↑ Miller, 1956.
  77. ↑ Kneis, Mölle, Richter, Rossmanith, 2005.
  78. ↑ Björklund, Husfeldt, 2008.

Литература

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .



Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии