Древесная ширина графа: различия между версиями

Один из основных способов применения понятий древесной ширины и древесной декомпозиции заключается в следующем: многие задачи, трудноразрешимые (например, NP-полные) в случае произвольных графов, становятся разрешимыми за полиномиальное или линейное время в случае графов с ограниченной древесной шириной. К числу задач, для которых может быть применена эта техника, относятся многие классические графовые и сетевые задачи – такие как нахождение гамильтонова контура, дерева Штейнера, вершинного покрытия, независимого множества и раскраски графа – однако она может применяться и к множеству других задач. Она также используется алгоритмом, разработанным Лауритценом и Шпигельхальтером [11], для решения задачи логического вывода на вероятностных сетях (байесовых или «сетях доверия»). Подобные алгоритмы обычно имеют следующий вид. Вначале вычисляется древесная декомпозиция ограниченной ширины, а затем выполняется динамический алгоритм, использующий эту древесную декомпозицию. Нередко время выполнения динамического алгоритма оказывается экспоненциальным относительно ширины используемой древесной декомпозиции, в силу чего ее желательно выбирать насколько возможно малой.