В теории графов путевая декомпозиция графа G — это, неформально, представление графа G в виде «утолщённого» пути, а путевая ширина графа G — это число, измеряющее, насколько граф G был утолщён. Более формально, путевая декомпозиция — это последовательности вершин подмножества графа G, такие, что конечные вершины каждого ребра появляются в одном из подмножеств и каждая вершина принадлежит (хотя бы) одному из множеств, а путевая ширина на единицу меньше размера наибольшего множества в такой декомпозиции. Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое числоМножество используемых в статье терминов можно найти во введении в диссертацию Ф. В. Фомина ().
Путевая ширина и путевая декомпозиция являются тесной аналогией с древовидной шириной и древовидной декомпозицией. Они играют ключевую роль в теории миноров графа — семейства графов, замкнутых относительно миноров графа и не включающих все леса могут быть охарактеризованы как имеющие ограниченную путевую ширину, и «вихри», возникающие в общей структурной теорией семейств графов, замкнутых по минорам, имеют ограниченную путевую ширину. Путевая ширина и графы с ограниченной путевой шириной имеют приложение в разработке СБИС, визуализации графов и компьютерной лингвистике.
Нахождение путевой ширины произвольных графов является NP-трудной задачей. Более того, NP-трудна даже аппроксимация путевой ширины точно. Однако эта задача является фиксированно-параметрически разрешимой — проверка, имеет ли граф путевую ширину k, может быть решена за время, которое линейно зависит от размера графа, но суперэкспоненциально от k Кроме того, для некоторых специальных классов графов, таких как деревья, путевая ширина может быть вычислена за полиномиальное время, независимое от k. Многие задачи теории графов можно эффективно решить на графах с ограниченной путевой шириной при помощи динамического программирования на путевой декомпозиции графа. Древовидную декомпозицию можно также использовать для оценки алгоритмов динамического программирования на графах с ограниченной древовидной шириной.
Определение
В первой знаменитой серии статей о минорах графа, Робертсон и Сеймур определили путевую декомпозицию графа G как последовательность подмножеств Xi вершин графа G с двумя свойствами: Для каждого ребра G, существует i такое, что обе конечные точки ребра принадлежат подмножеству Xi Для любых трёх индексов i ≤ j ≤ k, Второе из этих двух свойств эквивалентно требованию, что подмножества, содержащие любую вершину, образуют непрерывную подпоследовательность всей последовательности. На языке более поздней серии работ Робертсона и Сеймура о минорах графа путевая декомпозиция — это древовидная декомпозиция (X,T), в которой нижележащее дерево T декомпозиции является путём.
Ширина путевой декомпозиции определяется тем же способом, что и для древовидной декомпозиции, как maxi |Xi| − 1, а путевая ширина графа G равна минимальной ширине всех путевых декомпозиций графа G. Вычитание единицы из размера Xi в этом определении мало влияет на большинство приложений путевой ширины, но зато делает путевую ширину пути равной единице.
Альтернативные описания Как пишет Бодлаендер , путевая ширина может быть описана многими эквивалентными способами.
Склеивание последовательностей Древовидную декомпозицию можно описать как последовательность графов Gi. Эти графы склеены путём отождествления пар вершин в соседних графах последовательности. В результате образуется граф G. В качестве графов Gi можно взять порождённые подграфы множеств Xi в первом определении путевой декомпозиции, со склеиванием вершин в соседних порождённых подграфах, если эти вершины порождены той же самой вершиной из G. В другом направлении можно взять Xi в качестве множества вершин графов Gi. Ширина древовидной декомпозиции тогда на единицу меньше максимального числа вершин в одном из графов Gi.
Интервальная толщина
Путевая ширина любого графа G на единицу меньше наименьших кликового числа интервального графа, содержащего G в качестве подграфа. То есть для любой древовидной декомпозиции графа 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. Величину вершинного разделения ввели Эллис, Садбороу и Тёрнер и она равна путевой ширине графа G. Это следует из ранее упомянутой эквивалентности интервальных графов и кликовых чисел — если G является подграфом интервального графа I, представленного (как на рисунке) таким образом, что все концы интервалов различны, то порядок левых концов интервалов графа I имеют величину вершинного разделения на единицу меньше кликового числа графа I. В другом направлении, из линейного упорядочения графа G можно получить интервальное представление, в котором левая конечная точка интервала для вершины v является позицией в упорядочении, а правая конечная точка является позицией соседа v, который в упорядочении последний.
Вершинно-поисковое число Игра «поиск вершины» на графе — это вид игры преследования-уклонения, в которой множество преследователей совместно пытаются выследить беглеца, спрятавшегося в графе. Преследователи размещаются в вершинах графа, в то время как беглец может находиться на любом ребре графа, его местоположение и ходы преследователям не видны. Во время очередного хода некоторые (или все) преследователи могут перейти (произвольным образом, не обязательно вдоль рёбер) из одной вершины в другую, а беглец движется затем вдоль любого пути на графе, но не может проходить через занятые преследователями вершины. Беглец пойман, когда оба конца ребра, на котором он находится, заняты преследователями. Вершинно-поисковое число графа — это минимальное число преследователей, необходимых для гарантированной поимки беглеца вне зависимости от его поведения. Как показали Кироузис и Панадимитриу, вершинно-поисковое число графа равно его интервальной толщине. Оптимальной стратегией для преследователей служат ходы, в которых преследователи последовательно образуют разделяющие множества линейного упорядочивания с минимальной величиной вершинного разделения.
Границы
Любой граф с n вершинами и путевой шириной k имеет максимум рёбер, и максимальные графы с путевой шириной k (графы, к которым нельзя добавить ребро без увеличения путевой ширины) имеют в точности это число рёбер. Максимальный граф с путевой шириной k должен быть либо k-путём, либо k-гусеницей, т.е. одного из двух специальных видов k-дерева. k-дерево — это хордальный граф с в точности максимальными кликами, каждая из которых содержит вершин. В k-дереве, которое не является само по себе , каждая максимальная клика либо делит граф на две или более компоненты, либо содержит единичную листовую вершину, вершину, которая принадлежит только одной максимальной клике. k-путь — это k-дерево с максимум двумя листьями, а k-гусеница — это k-дерево, которую можно разбить на k-путь и множество k-листов, каждый из которых смежен с сепаратором k-клики k-пути. В частности, максимальные графы путевой ширины единица — это в точности графы-гусеницы .
Поскольку путевые декомпозиции являются специальными случаями древовидных декомпозиций, путевая ширина любого графа больше либо равна его древовидной ширине. Путевая ширина также меньше или равна ширине разреза, минимального числа рёбер, пересекающих любое сечение между вершинами с меньшим индексом и большим индексом в оптимальном линейном упорядочении вершин графа. Это следует из факта, что величина вершинного разделения, число вершин с меньшим индексом с соседами, имеющими больший индекс, не больше числа разрезающих рёбер. По такой же причине ширина разреза не превосходит путевой ширины, умноженной на максимальную степень вершин в данном графе.
Любой лес с n вершинами имеет путевую ширину O(log n)Шеффлер () даёт более сильную границу log3(2n + 1) путевой ширины леса с n вершинами.. Для леса можно всегда найти постоянное число вершин, удаление которых приводит к лесу, который можно разбить на два меньших леса с максимум 2n/3 вершин в каждом из этих лесов. Линейное упорядочение, образованное рекурсивным применением такого разбиения, имеет логарифмическое поисковое число для вершин. Та же техника, применённая к древовидной декомпозиции графа, показывает, что если древовидная ширина графа G с n вершинами равна t, то путевая ширина графа G равна O(t log n). Поскольку внешнепланарные графы, параллельно-последовательные графы и графы Халина все имеют ограниченную древовидную ширину, все они имеют максимум логарифмическую путевую ширину.
Кроме того, что путевая ширина связана с древовидной шириной, она связана с кликовой шириной и шириной разреза через рёберные графы. Рёберный граф L(G) графа G имеет вершину для каждого ребра графа G и две вершины в L(G) смежны, если соответствующие два ребра имеют G общие конечные точки. Любое семейство графов имеет ограниченную путевую ширину тогда и только тогда, когда его рёберные графы имеют ограниченную линейную кликовую ширину. Линейная кликовая ширина заменяет операцию объединения в определении кликовой ширины на операцию присоединения отдельной новой вершины.. Если связный граф с тремя или более вершинами имеет максимальную стпепень 3, его ширина разреза равна величине вершинного разделения его рёберного графа.