4551
правка
Путевая ширина графа: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Сжатие дуги или ее удаление не может привести к повышению путевой ширины. Согласно теории о минорах графов, из этого следует, что для любого фиксированного k существует конечное число минимальных относительно миноров графов, путевая ширина которых превышает k; обозначим это множество графов за <math>\mathfrak{B}_k</math>. Проверить, содержит ли граф G фиксированный граф в качестве минора, можно за полиномиальное время [27]. Таким образом, из знания <math>\mathfrak{B}_k</math> следует возможность построения полиномиального по времени алгоритма для выяснения верности соотношения branchwidth(G) < | Сжатие дуги или ее удаление не может привести к повышению путевой ширины. Согласно теории о минорах графов, из этого следует, что для любого фиксированного k существует конечное число минимальных относительно миноров графов, путевая ширина которых превышает k; обозначим это множество графов за <math>\mathfrak{B}_k</math>. Проверить, содержит ли граф G фиксированный граф в качестве минора, можно за полиномиальное время [27]. Таким образом, из знания <math>\mathfrak{B}_k</math> следует возможность построения полиномиального по времени алгоритма для выяснения верности соотношения <math>branchwidth(G) \le k </math> для любого фиксированного k. К сожалению, <math>\mathfrak{B}_k</math> известно только для небольших значений k; в частности, <math>\mathfrak{B}_0 = \big\{ P_2 \big\} </math>}; <math>\mathfrak{B}_1 = \big\{ P_4 , K_3 \big\} </math>; <math>\mathfrak{B}_2 = \big\{ K_4 \big\} </math>, а <math>\mathfrak{B}_3 = \big\{ K_5; V_8; M_6; Q_3 \big\} </math> (здесь <math>K_r \, </math> – это клика из r вершин; <math>P_r \, </math> – путь из r дуг; <math>V_8 \, </math> – граф, получаемый из контура с 8 вершинами, если соединить все пары вершин с расстоянием в контуре, равным 4; <math>M_6 \, </math> – октаэдр; а <math>Q_3 \, </math> – трехмерный куб). Однако для любого фиксированного k можно построить линейный относительно <math>n = |V(G)| \, </math> алгоритм, который определяет, выполняется ли для входного графа G соотношение <math>branchwidth(G) \le k </math> и, в случае положительного ответа, выдает соответствующую декомпозицию в форме ветвления [3]. Технически из этого следует, что нахождение ответа на вопрос, верно ли для конкретного графа G соотношение <math>branchwidth(G) \le k </math>, в отношении параметра k является FPT-сложной задачей (иначе говоря, принадлежит к параметризованному [[класс сложности|классу сложности]] FPT). Более детальные сведения о параметризованных алгоритмах и классах сложности можно найти в [12]. Алгоритм, приведенный в статье [3], довольно сложен и использует технику характеристических последовательностей, которая также применялась для доказательства аналогичного результата в случае древесной ширины. Для конкретных случаев с <math>k \le 3 \, </math> существуют более простые алгоритмы, использующие технику «правило редукции» [4]. Следует понимать, что <math>\mathfrak{B}_4</math> остается неизвестным, несмотря на то, что некоторые его элементы уже были обнаружены (включая графы додекаэдра и икосаэдра). Существует несколько алгоритмов, которые для заданного k могут за время <math>2^{O(k)} \cdot n^{O(1)}</math> либо определить верность утверждения о том, что путевая ширина данного графа G составляет не менее k, либо построить декомпозицию в форме ветвления ширины O(k) ([26]). Эти результаты можно обобщить, чтобы вычислить путевую ширину матроидов и даже более общие параметры. | ||
Точный алгоритм вычисления путевой ширины был приведен в [14]. Он имеет сложность <math>O((2 \cdot \sqrt{3})^n \cdot n^{O(1)})</math>. Алгоритм использует особые свойства путевой ширины (см. также [24]). | |||
В отличие от древесной ширины, максимальные по количеству дуг графы заданной путевой ширины не так легко поддаются характеризации (в случае древесной ширины они представляют собой просто k-деревья, то есть хордальные графы, все максимальные клики которых имеют размер k + 1). Алгоритм генерации таких графов, приведенный в [23], выявляет несколько структурных задач, связанных с этим параметром. | В отличие от древесной ширины, максимальные по количеству дуг графы заданной путевой ширины не так легко поддаются характеризации (в случае древесной ширины они представляют собой просто k-деревья, то есть хордальные графы, все максимальные клики которых имеют размер k + 1). Алгоритм генерации таких графов, приведенный в [23], выявляет несколько структурных задач, связанных с этим параметром. | ||
Известно, что большое число теоретико-графовых задач может быть решено за линейное время в случае, если их входные данные ограничены графами небольшой (иначе говоря, фиксированной) древесной или путевой ширины [2]. | Известно, что большое число теоретико-графовых задач может быть решено за линейное время в случае, если их входные данные ограничены графами небольшой (иначе говоря, фиксированной) древесной или путевой ширины [2]. | ||
[[Файл:Treewidth.png]] | [[Файл:Treewidth.png]] | ||
Рис. 1. Путевая ширина графа | Рис. 1. Путевая ширина графа | ||
Пример графа и его декомпозиция в форме ветвления с путевой шириной 3 | Пример графа и его декомпозиция в форме ветвления с путевой шириной 3 | ||
