Путевая ширина

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