Русская Википедия:Путевая ширина
В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» путиШаблон:Sfn, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит (хотя бы) одному из множествШаблон:Sfn, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции. Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое числоШаблон:Sfn[1].
Путевая ширина и путевая декомпозиция являются тесной аналогией с древесной шириной и древесной декомпозицией. Они играют ключевую роль в теории миноров графа — семейства графов, замкнутых относительно миноров графа и не включающих все леса могут быть охарактеризованы как имеющие ограниченную путевую ширинуШаблон:Sfn, и «вихри», возникающие в общей структурной теорией семейств графов, замкнутых по минорам, имеют ограниченную путевую ширинуШаблон:Sfn. Путевая ширина и графы с ограниченной путевой шириной имеют приложение в разработке СБИС, визуализации графов и компьютерной лингвистике.
Задача нахождения путевой ширины произвольных графов является NP-трудной. Более того, NP-трудна даже задача аппроксимации путевой ширины точно[2]Шаблон:Sfn. Однако эта задача является фиксированно-параметрически разрешимой — проверка, имеет ли граф путевую ширину k, может быть решена за время, которое линейно зависит от размера графа, но суперэкспоненциально от k[3] Кроме того, для некоторых специальных классов графов, таких как деревья, путевая ширина может быть вычислена за полиномиальное время, независимое от kШаблон:Sfn[4]. Многие задачи теории графов можно эффективно решить на графах с ограниченной путевой шириной при помощи динамического программирования на путевой декомпозиции графаШаблон:Sfn. Древесную декомпозицию можно также использовать для оценки Шаблон:Не переведено 5 алгоритмов динамического программирования на графах с ограниченной древесной ширинойШаблон:Sfn.
Определение
В первой знаменитой серии статей о минорах минорах графа Робертсон и СеймурШаблон:Sfn определили путевую декомпозицию графа G как последовательность подмножеств Xi вершин графа G с двумя свойствами:
- Для каждого ребра G, существует i такое, что обе конечные точки ребра принадлежат подмножеству Xi
- Для любых трёх индексов i ≤ j ≤ k, Шаблон:Nowrap
Второе из этих двух свойств эквивалентно требованию, что подмножества, содержащие любую вершину, образуют непрерывную подпоследовательность всей последовательности. На языке более поздней серии работ Робертсона и Сеймура о минорах графа путевая декомпозиция — это древесная декомпозиция (X,T), в которой нижележащее дерево T декомпозиции является путём.
Ширина путевой декомпозиции определяется тем же способом, что и для древесной декомпозиции, как maxi |Xi| − 1, а путевая ширина графа G равна минимальной ширине всех путевых декомпозиций графа G. Вычитание единицы из размера Xi в этом определении мало влияет на большинство приложений путевой ширины, но зато делает путевую ширину пути равной единице.
Альтернативные описания
Как пишет БодлаендерШаблон:Sfn, путевая ширина может быть описана многими эквивалентными способами.
Склеивание последовательностей
Древесную декомпозицию можно описать как последовательность графов Gi, которые склеены путём отождествления пар вершин в соседних графах последовательности, и в результате этого склеивания образуется граф G. В качестве графов Gi можно взять порождённые подграфы множеств Xi в первом определении путевой декомпозиции, со склеиванием вершин в соседних порождённых подграфах, если эти вершины порождены той же самой вершиной из G. В другом направлении можно взять Xi в качестве множеств вершин графов Gi. Ширина древесной декомпозиции тогда на единицу меньше максимального числа вершин в одном из графов GiШаблон:Sfn.
Интервальная толщина
Путевая ширина любого графа G на единицу меньше наименьших кликового числа интервального графа, содержащего G в качестве подграфаШаблон:Sfn. То есть для любой древесной декомпозиции графа G можно найти интервальный суперграф, и для любого интервального суперграфа G можно найти древесную декомпозицию графа G, ширина декомпозиции которой на единицу меньше кликового числа интервального графа.
В одном направлении, предположим, что древесная декомпозиция графа G задана. Тогда можно представить вершины декомпозиции как точки на прямой (в том порядке, в котором они входят в путь) и представить каждую вершину v как замкнутый интервал, имеющий эти точки в качестве конечных точек. Например, пусть (X1, . . . , Xr) — путевая декомпозиция графа G, точки на прямой — [1, . . . , r], тогда представление вершины v — это интервал <math>[min\{i|v \in X_i\},max\{i|v \in X_i\}]</math>. Тогда древесная декомпозиция вершин, содержащих v, соответствует представляющим (т.е. конечным точкам) интервала для v. Граф пересечений интервалов, образованный из вершин G — это интервальный граф, содержащий G в качестве подграфа. Его максимальные клики задаются множеством интервалов, содержащих представляющие точки, и их размер наибольшей клики на единицу больше путевой ширины графа G.
В другом направлении, если G — подграф интервального графа с кликовым числом p + 1, то граф G имеет древесную декомпозицию ширины p, вершины которой заданы максимальными кликами интервального графа. Например, интервальный граф, показанный с его интервальным представлением на рисунке, имеет древесную декомпозицию с пятью вершинами, соответствующими пяти максимальным кликам ABC, ACD, CDE, CDF и FG. Размер максимальной клики равен трём, а ширина этой древесной декомпозиции равна двум.
Эта эквивалентность между путевой шириной и интервальной толщиной является тесной аналогией с эквивалентностью между древесной шириной и минимальным кликовым числом (минус единица) хордального графа, для которого данный граф является подграфом. Интервальные графы являются специальным случаем хордальных графов, а хордальные графы можно представить в виде графов пересечений поддеревьев общих деревьев, что обобщает подход, при котором интервальные графы интерпретируются как графы пересечений подпутей пути.
Величина вершинного разделения
Предположим, что вершины графа G линейно упорядочены. Тогда величина вершинного разделения графа G — это наименьшее число s, такое, что для каждой вершины v максимум s вершин предшествуют v в упорядочении, которые имеют v или одну из следующих за ней вершин в окрестности. Величина вершинного разделения графа G — это минимальная величина вершинного разделения любого линейного любого линейного упорядочения графа G. Величину вершинного разделения ввели Эллис, Садбороу и ТёрнерШаблон:Sfn и она равна путевой ширине графа GШаблон:SfnШаблон:Sfn. Это следует из ранее упомянутой эквивалентности интервальных графов и кликовых чисел — если G является подграфом интервального графа I, представленного (как на рисунке) таким образом, что все концы интервалов различны, то порядок левых концов интервалов графа I имеют величину вершинного разделения на единицу меньше кликового числа графа I. В другом направлении, из линейного упорядочения графа G можно получить интервальное представление, в котором левая конечная точка интервала для вершины v является позицией в упорядочении, а правая конечная точка является позицией соседа v, который в упорядочении последний.
Вершинно-поисковое число
Игра «поиск вершины» на графе — это вид игры преследования-уклонения, в которой множество преследователей совместно пытаются выследить беглеца, спрятавшегося в графе. Преследователи размещаются в вершинах графа, в то время как беглец может находиться на любом ребре графа, его местоположение и ходы преследователям не видны. Во время очередного хода некоторые (или все) преследователи могут перейти (произвольным образом, не обязательно вдоль рёбер) из одной вершины в другую, а беглец движется затем вдоль любого пути на графе, но не может проходить через занятые преследователями вершины. Беглец пойман, когда оба конца дуги, на которой он находится, заняты преследователями. Вершинно-поисковое число графа — это минимальное число преследователей, необходимых для гарантированной поимки беглеца вне зависимости от его поведения. Как показали Кироузис и ПанадимитриуШаблон:Sfn, вершинно-поисковое число графа равно его интервальной толщине. Оптимальной стратегией для преследователей служат ходы, в которых преследователи последовательно образуют разделяющие множества линейного упорядочивания с минимальной величиной вершинного разделения.
Границы
Любой граф с n вершинами и путевой шириной k имеет максимум Шаблон:Nowrap рёбер, и максимальные графы с путевой шириной k (графы, к которым нельзя добавить ребро без увеличения путевой ширины) имеют в точности это число рёбер. Максимальный граф с путевой шириной k должен быть либо k-путём, либо k-гусеницей, т.е. одного из двух специальных видов k-дерева. k-дерево — это хордальный граф с в точности Шаблон:Nowrap максимальными кликами, каждая из которых содержит Шаблон:Nowrap вершин. В k-дереве, которое не является само по себе Шаблон:Nowrap, каждая максимальная клика либо делит граф на две или более компоненты, либо содержит единичную листовую вершину, вершину, которая принадлежит только одной максимальной клике. k-путь — это k-дерево с максимум двумя листьями, а k-гусеница — это k-дерево, которую можно разбить на k-путь и множество k-листов, каждый из которых смежен с сепаратором k-клики k-пути. В частности, максимальные графы путевой ширины единица — это в точности графы-гусеницы Шаблон:Sfn.
Поскольку путевые декомпозиции являются специальными случаями древесных декомпозиций, путевая ширина любого графа больше либо равна его древесной ширине. Путевая ширина также меньше или равна ширине разреза, минимального числа рёбер, пересекающих любое сечение между вершинами с меньшим индексом и большим индексом в оптимальном линейном упорядочении вершин графа. Это следует из факта, что величина вершинного разделения, число вершин с меньшим индексом с соседами, имеющими больший индекс, не больше числа разрезающих рёберШаблон:SfnШаблон:Sfn. По такой же причине ширина разреза не превосходит путевой ширины, умноженной на максимальную степень вершин в данном графеШаблон:SfnШаблон:Sfn.
Любой лес с n вершинами имеет путевую ширину O(log n)Шаблон:SfnШаблон:Sfn[5]. Для леса можно всегда найти постоянное число вершин, удаление которых приводит к лесу, который можно разбить на два меньших леса с максимум 2n/3 вершин в каждом из этих лесов. Линейное упорядочение, образованное рекурсивным применением такого разбиения, имеет логарифмическое поисковое число для вершин. Та же техника, применённая к древесной декомпозиции графа, показывает, что если древесная ширина графа G с n вершинами равна t, то путевая ширина графа G равна O(t log n)Шаблон:SfnШаблон:Sfn. Поскольку внешнепланарные графы, параллельно-последовательные графы и графы Халина все имеют ограниченную древесную ширину, все они имеют максимум логарифмическую путевую ширину.
Кроме того, что путевая ширина связана с древесной шириной, она связана с кликовой шириной и шириной разреза через рёберные графы. Рёберный граф L(G) графа G имеет вершину для каждого ребра графа G и две вершины в L(G) смежны, если соответствующие два ребра имеют G общие конечные точки. Любое семейство графов имеет ограниченную путевую ширину тогда и только тогда, когда его рёберные графы имеют ограниченную линейную кликовую ширину, где линейная кликовая ширина заменяет операцию объединения в определении кликовой ширины на операцию присоединения отдельной новой вершиныШаблон:Sfn. Если связный граф с тремя или более вершинами имеет максимальную стпепень 3, его ширина разреза равна величине вершинного разделения его рёберного графаШаблон:Sfn.
В любом планарном графе путевая ширина в худшем случае пропорциональна квадратному корню от числа вершинШаблон:Sfn. Один из способов поиска путевой декомпозиции с такой шириной — (подобно путевой декомпозиции с логарифмической шириной лесов, описанной выше) использовать теорему о планарном разбиении, чтобы найти множество из O(√n) вершин, удаление которых разбивает граф на два подграфа с максимум 2n/3 вершинами в каждом, и соединить рекурсивно построенные для этих двух подграфов путевые декомпозиции. Та же техника применима к любому классу графов, для которых выполняется подобная теорема о разбиенииШаблон:Sfn. Поскольку любое семейство графов, замкнутое относительно взятия миноров, как и в случае планарных графов, имеет разбивающее множество вершин размера O(√n)Шаблон:Sfn, отсюда следует, что путевая ширина графов в любом фиксированном замкнутом относительно миноров семействе снова равна O(√n). Для некоторых классов планарных графов путевая ширина графа и путевая ширина его двойственного графа должны лежать в интервале, границы которого линейно зависят от значений — такие границы известны для двусвязных внешнепланарных графовШаблон:SfnШаблон:Sfn и для графов многогранниковШаблон:SfnШаблон:Sfn. Для двусвязных планарных графов путевая ширина двойственного графа меньше, чем путевая ширина рёберного графаШаблон:Sfn. Остаётся открытым вопрос, являются ли путевые ширины планарного графа и его двойственного всегда в линейных границах для остальных случаев.
Для некоторых классов графов доказано, что путевая ширина и древесная ширина всегда равны друг другу — это верно для кографовШаблон:Sfn, графов перестановки Шаблон:Sfn, дополнений графов сравнимостиШаблон:Sfn и графов сравнимости Шаблон:Не переведено 5Шаблон:Sfn.
Шаблон:Unsolved В любом кубическом графе, или, более обще, любом графе с максимальной степенью вершин 3, путевая ширина не превосходит n/6 + o(n), где n — число вершин графа. Существуют кубические графы с путевой шириной 0.082n, но неизвестно, как сократить этот разрыв между Шаблон:Не переведено 5 и верхней границей n/6Шаблон:Sfn.
Вычисление путевых декомпозиций
Определение, не превосходит ли путевая ширина заданное значение k для заданного графа, является NP-полной задачей, если k является входным параметром [2]. Наиболее известные временные границы (Шаблон:Не переведено 5) вычисления путевой ширины произвольного графа с n вершинами имеют вид O(2n nc) при некоторой константе cШаблон:Sfn. Тем не менее, известны некоторые алгоритмы вычисления путевой декомпозиции с большей эффективностью, если путевая ширина мала, если класс входных графов ограничен, или требуется вычислить путевую ширину приближённо.
Фиксированно-параметрически разрешимость
Путевая ширина Шаблон:Не переведено 5 — для любой постоянной k можно проверить, не превосходит ли путевая ширина величину k, и если не превосходит, найти путевую декомпозицию ширины k за линейное время [3]. В целом, эти алгоритмы работают в два этапа. На первом этапе используется предположение, что граф имеет путевую ширину k, для поиска путевой декомпозиции или древесной декомпозиции. Эта декомпозиция не оптимальна, но её ширина может быть ограничена функцией от k. На втором этапе применяется алгоритм динамического программирования для поиска оптимальной декомпозиции. Однако временные границы для известных алгоритмов этого типа экспоненциальны от k2 и не представляют практического интереса, разве что для малых значений kШаблон:Sfn. Для случая k = 2 Фляйтер дал алгоритм с линейным временем работы, основанный на структурной декомпозиции графов с путевой шириной 2 Шаблон:Sfn.
Специальные классы графов
Бодлаендер Шаблон:Sfn дал обозрение сложности задач вычисления путевой ширины на различных специальных классах графов. Определение, превосходит ли путевая ширина графа G величину k, остаётся NP-полной задачей, если G берётся из графов ограниченной степениШаблон:Sfn, планарные графыШаблон:Sfn, планарных графов ограниченной степениШаблон:Sfn, хордальных графовШаблон:Sfn, хордальных домино[6], дополнений графов сравнимостиШаблон:Sfn, и двудольных дистанционно-наследуемых графовШаблон:Sfn. Отсюда немедленно следует, что задача также NP-полна для семейств графов, содержащих двудольные дистанционно-наследуемые графы, включая двудольные графы, хордальные двудольные графы дистанционно-наследуемые графы и круговые графыШаблон:Sfn.
Однако путевую ширину можно вычислить за линейное время для деревьев и лесов [4]. Можно вычислить эту величину за полиномиальное время для графов ограниченной древесной ширины, в которые входят параллельно-последовательные графы, внешнепланарные графы и графы Халина [3], а также расщепляемые графыШаблон:SfnШаблон:Sfn, дополнения хордальных графов [7], графы перестановкиШаблон:Sfn, кографыШаблон:Sfn, графы дуг окружностиШаблон:Sfn, графы сравнимости интервальных порядковШаблон:Sfn, и, конечно, сами интервальные графы, поскольку для них путевая ширина просто на единицу меньше максимального числа интервального накрытия любой точки в интервальном представлении графа.
Аппроксимационные алгоритмы
NP-трудной задачей является аппроксимация путевой ширины графа аддитивной константойШаблон:Sfn. Лучший известный аппроксимационный коэффициент аппроксимационных алгоритмов полиномиального времени для путевой ширины равен O((log n)3/2)Шаблон:Sfn. Ранние аппроксимационные алгоритмы для путевой ширины можно найти у Бодлаендера, Гилберта, Хафштейнссона, КлоксаШаблон:Sfn и ГухаШаблон:Sfn. Для аппроксимации ограниченных классов графов см. книгу Клокса и БодлаендераШаблон:Sfn.
Миноры графа
Минор графа G — это другой граф, образованный из G путём стягивания рёбер, удаления рёбер и вершин. Миноры графа имеют глубокую теорию, в которой некоторые некоторые важные результаты используют путевую ширину.
Исключение леса
Если семейство F графов замкнуто по отношению к операции взятия миноров (любой минор члена семейства F также содержится в F), тогда по теореме Робертсона – Сеймура семейство F можно охарактеризовать как графы, не содержащие миноров из X, где X — конечное множество запрещённых миноров Шаблон:Sfn. Например, теорема Вагнера утверждает, что планарные графы — это графы, которые не содержат ни полного графа K5, ни полного двудольного графа K3,3 в качестве миноров. Во многих случаях свойства F и свойства X тесно связаны, и первый результат такого типа получили Робертсон и Сеймур Шаблон:Sfn и он связывает существование ограниченной путевой ширины с наличием леса в семействе запрещённых миноров. Конкретнее, определим семейство F графов как имеющее ограниченную путевую ширину, если существует константа p, такая, что любой граф из F имеет путевую ширину, не превосходящую p. Тогда минорно-замкнутое семейство F имеет ограниченную путевую ширину тогда и только тогда, когда множество X запрещённых миноров для F включает хотя бы один лес.
В одном направлении этот результат можно доказать прямо — а именно, что если X не содержит хотя бы один лес, то свободные от X-миноров графы не имеет ограниченной путевой ширины. В этом случае свободные от X-миноров графы включают все леса, и, в частности, совершенные бинарные деревья. Но совершенные бинарные деревья с 2k + 1 уровнями имеют путевую ширину k, так что в этом случае свободные от X-миноров графы имеют неограниченную путевую ширину. В обратном направлении, если X содержит лес с n вершинами, то свободные от X-миноров графы имеют путевую ширину, не превосходящую n − 2Шаблон:SfnШаблон:SfnШаблон:Sfn.
Оценки путевой ширины
Свойство иметь путевую ширину не больше p является, само по себе, замкнутым по взятию миноров свойством — если G имеет путевую декомпозицию с шириной, не превосходящей p, то та же самая путевая декомпозиция остаётся верной, если удалить любое ребро из G, а также любая вершина может быть удалена из графа G и его путевой декомпозиции без увеличения ширины. Стягивание ребра также может быть завершено без увеличения ширины декомпозиции путём слияния подпутей, представляющих два конца стягиваемого ребра. Таким образом, графы с путевой шириной, не превосходящей p, могут быть охарактеризованы множеством Xp запрещённых миноровШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
Хотя Xp обязательно включает по меньшей мере один лес, неверно, что все графы в Xp являются лесами. Например, X1 состоит из двух графов, дерева с семью вершинами и треугольника K3. Однако множество деревьев в Xp можно точно описать — это в точности те деревья, которые можно образовать из трёх деревьев из Xp − 1 путём образования нового корня и соединения его рёбрами с произвольно выбранными вершинами меньших деревьев. Например, дерево с семью вершинами в X1 образовано из деревьев с двумя вершинами (одно ребро) из X0. Основываясь на этом построении, можно показать, что число запрещённых миноров в Xp не меньше (p!)2Шаблон:SfnШаблон:SfnШаблон:Sfn. Полное множество X2 запрещённых миноров для графов с путевой шириной 2 вычислено. Это множество содержит 110 различных графовШаблон:Sfn.
Структурная теория
Структурная теорема графов для семейств замкнутых по минорам графов утверждает, что для любого семейства F, в котором графы могут быть разложены на cуммы по клике графов, которые могут быть вложены в поверхности ограниченного рода вместе с ограниченным числом верхушек и вихрей для каждой компоненты суммы по клике. Верхушка — это вершина, которая смежна со всеми вершинами компоненты, а вихрь — это граф ограниченной путевой ширины, который приклеивается к грани компоненты с вложением ограниченного рода. Циклический порядок вершин вокруг грани, в которую вихрь вложен, должен быть совместим с древесной декомпозицией вихря в том смысле, что разрыв цикла для образования линейного упорядочения должен привести к упорядочению с ограниченной величиной вершинного разделенияШаблон:Sfn. Эта теория, в которой путевая ширина тесно связана с произвольными семействами графов, замкнутых относительно миноров, имеет важное алгоритмическое применениеШаблон:Sfn.
Приложения
СБИС
При разработке СБИС задача разделения вершин первоначально изучалась как путь разделения цепей на меньшие подсистемы с малым числом компонент на границе между системамиШаблон:Sfn.
Отцуки, Мори, Кух и КашивабараШаблон:Sfn использовали интервальную толщину для моделирования числа проводников, необходимых в одномерном расположении цепей СБИС, образованных множеством модулей, которые необходимо соединить системой сетей. В их модели можно образовать граф, в котором вершины представляют цепи и в которой две вершины соединены ребром, если их цепи соединены к одному и тому же модулю. То есть если модули и цепи понимаются как вершины и гиперрёбра гиперграфа, то граф, образованный из них, является рёберным графом гиперграфа. Интервальное представление суперграфа этого рёберного графа вместе с раскраской суперграфа описывает расположение цепей вдоль горизонтальных дорожек (одна дорожка на каждый цвет), так что модули могут быть расположены вдоль дорожек в линейном порядке и соединены с нужными цепями. Из факта, что интервальные графы являются совершеннымиШаблон:Sfn, следует, что число цветов, необходимых для оптимальной раскладки такого типа, равно кликовому числу интервального дoполнения графа цепей.
Матричная укладка переключателейШаблон:Sfn является специфическим видом КМОП СБИС укладки для цепей алгебры логики. В матричных укладках переключателей сигнал распространяется вдоль "линий" (вертикальных отрезков), в то время как каждый переключатель образуется последовательностью элементов, располагающихся на горизонтальном отрезке. Таким образом, горизонтальные отрезки для каждого переключателя должны пересекать вертикальные отрезки для каждой линии, которая служит входом или выходом переключателя. Как и в укладках Отцуки, Мори, Куха и КашивабараШаблон:Sfn укладка такого типа, минимизирующая число вертикальных прямых, может быть вычислена путём вычисления путевой ширины графа, имеющего прямые в качестве вершин, а пары прямых, принадлежащих переключателю, в качестве рёберШаблон:Sfn. Тот же алгоритмический подход может быть также использован для моделирования задач укладки в Шаблон:Не переведено 5Шаблон:SfnШаблон:Sfn.
Визуализация графов
Путевая ширина имеет несколько приложений для визуализации графов:
- Минимальные графы, имеющие заданное число пересечений, имеют путевую ширину, ограниченную функцией от числа пересеченийШаблон:Sfn.
- Число параллельных прямых, на которых можно расположить вершины дерева без пересечения рёбер (при различных естественных ограничениях на способы, которыми смежные вершины могут быть помещены на прямых с учётом последовательности прямых) пропорционально путевой ширине дереваШаблон:Sfn.
- k-пересечённый h-уровневый рисунок графа G — это расположение вершин графа G на h различных горизонтальных прямых с рёбрами в виде монотонных (представленных ломаными) путей между прямыми, в котором имеется не более k пересечений. Графы с таким представлением имеют путевую ширину, ограниченную функцией от h и k. Таким образом, если величины h и k постоянны, можно за линейное время определить, имеется ли у графа k-пересечённый h-уровневый рисунокШаблон:Sfn.
- Граф с n вершинами и путевой шириной p может быть вложен в трёхмерную решётку размера Шаблон:Nowrap таким образом, что никакие два ребра (представленные прямолинейными отрезками между точками решётки) не пересекают друг друга. Таким образом, графы ограниченной путевой ширины имеют вложения этого типа с линейным объёмомШаблон:Sfn.
Проектирование компиляторов
При трансляции высокоуровневых языков программирования путевая ширина возникает в задаче переупорядочения линейного кода (то есть кода без управляющей логики — переходов и циклов) таким образом, что все значения, вычисленные в коде, могут быть в машинные регистры, а не вытеснены в основную память. В этом приложении оттранслированный код представляется в виде направленного ациклического графа (НАГ), в котором вершины представляют входные значения для кода и значения, вычисленные в результате операций внутри кода. Ребро из вершины x в вершину y в этом НАГ представляет факт, что значение x является одним из входных параметров для операции y. Топологическая сортировка вершин в этом НАГ представляет правильную сортировку кода, а число регистров, нужных для выполнения кода в этом порядке задаётся величиной вершинного разделения упорядоченияШаблон:Sfn.
Для любого фиксированного числа w регистров в машине можно определить за линейное время, может ли фрагмент линейного кода быть переупорядочен так, что для кода потребуется максимум w регистров. Если величина вершинного разделения топологического упорядочения не превосходит w, минимальное вершинное разделение среди всех упорядочений не может быть больше, так что неориентированные графы, образованные игнорированием ориентации НАГ, описанного выше, должны иметь путевую ширину, не превосходящую w. Можно проверить, верно ли это с помощью известных фиксированно-параметрически разрешимых алгоритмов для путевой ширины, и если верно, найти путевую декомпозицию для неориентированных графов за линейное время в предположении, что w является константой. Как только древесная декомпозиция найдена, топологическое упорядочение с шириной w (если такое существует) может быть найдено с использованием динамического программирования, опять же за линейное времяШаблон:Sfn.
Лингвистика
Карнаи и ТуцаШаблон:Sfn описали приложение путевой ширины для обработки естественного языка. В этом приложении предложения моделируются в виде графов, в которых вершины представляют слова, а рёбра представляют связи между словами. Например, если прилагательное модифицирует существительное, то граф имеет ребро между этими двумя словами. Ввиду ограниченного объёма кратковременной человеческой памяти МиллерШаблон:Sfn, Корнаи и Туца утверждают, что этот граф должен иметь ограниченную путевую ширину (конкретнее, они утверждают, что эта путевая ширина не превосходит шести), в противном случае люди не могли бы распознавать речь правильно.
Экспоненциальные алгоритмы
Многие задачи теории графов могут быть эффективно решены на графах с малой путевой шириной при помощи динамического программирования, опираясь на путевую декомпозицию графаШаблон:Sfn. Например, если линейное упорядочение вершин графа G с n вершинами задано и величина вершинного разделения равна w, то можно найти наибольшее независимое множество графа G за время Шаблон:NowrapШаблон:Sfn. На графе с ограниченной путевой шириной этот подход ведёт к фиксированно-параметрически разрешимым алгоритмам, параметризованным по путевой ширинеШаблон:Sfn. Такие результаты не часто встречаются в литературе, поскольку они принадлежат группе похожих алгоритмов, параметризованных по древесной ширине. Однако путевая ширина появляется даже в алгоритмах динамического программирования, основанных на древесной ширине, при измерении Шаблон:Не переведено 5 этих алгоритмовШаблон:Sfn.
Тот же самый метод динамического программирования может быть применён к графам с неограниченной путевой шириной, что приводит к алгоритмам, решающим непараметризованные задачи на графах за экспоненциальное время. Например, комбинация подхода динамического программирования с фактом, что кубические графы имеют путевую ширину n/6 + o(n), показывает, что для кубических графов максимальное независимое множество можно построить за время O(2n/6 + o(n)), что быстрее известных до этого методовШаблон:Sfn. Похожий подход ведёт к улучшенным алгоритмам экспоненциального времени для задач максимального разреза и минимального доминирующего множества для кубических графовШаблон:Sfn и для некоторых других NP-трудных оптимизационных задачШаблон:SfnШаблон:Sfn.
См. также
- Интервальная размерность графа, другой путь измерения сложности произвольных графов в терминах интервальных графов
- Глубина дерева, число, которое ограничено для минорно-замкнутых семейств графов тогда и только тогда, если семейство не содержит пути
- Вырожденность, мера разреженности графа, которая не больше путевой ширины графа
- Шаблон:Не переведено 5, другая NP-полная задача оптимизация, использующая линейные укладки графов
- Число Стралера, мера плотности корневых деревьев, определяемое подобно путевой ширине неориентированных деревьев
Примечания
Литература
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга. As cited by Шаблон:Harvtxt.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:СтатьяШаблон:Недоступная ссылка.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Книга.
- Шаблон:Статья.
- Шаблон:Статья.
- Шаблон:Статья
- ↑ Множество используемых в статье терминов можно найти во введении в диссертацию Ф. В. Фомина (Шаблон:Harv)
- ↑ 2,0 2,1 Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb.
- ↑ 3,0 3,1 3,2 Шаблон:Harvtxt; Шаблон:Harvtxt
- ↑ 4,0 4,1 Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvnb; Шаблон:Harvtxt.
- ↑ Шеффлер (Шаблон:Harvtxt) даёт более сильную границу log3(2n + 1) путевой ширины леса с n вершинами.
- ↑ Шаблон:Harvnb. Хордальное домино — это хордальный граф, в котором любая вершина принадлежит максимум двум максимальным кликам
- ↑ Гарбе (Шаблон:Harvtxt) приписывает этот результат тезисам диссертации Тона Клокса 1993 года. Алгоритм полиномиального времени Гарбе для графов сравнимости интервальных упорядочений обобщает этот результат, поскольку любой хордальный граф должен быть графом сравнимости такого типа.
