Аноним

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

Материал из WEGA

Древесная ширина графа (посмотреть исходный код)

Версия от 22:49, 10 июля 2016

1075 байт убрано ,  10 июля 2016
→‎Постановка задачи
Строка 28: Строка 28:


== Постановка задачи ==
== Постановка задачи ==
Древесная ширина графа определяется в терминах древесной декомпозиции. Древесная декомпозиция графа G = (V, E) представляет собой пару <math>( \{ X_i \; | \; i \in I \}, T = (I, F))</math>, где <math>\{ X_i \; | \; i \in I \}</math> – набор подмножеств V, называемых контейнерами, а T – дерево, такое, что


• <math>\bigcup_{i \in I} \; X_i = V</math>


• Для всех <math>\{ v, w \} \in E</math> существует <math>i \in I \;</math>, такое, что <math>v, w \in X_i \;</math>.
Рис. 1. Граф и его древесная декомпозиция ширины 2


• Для всех <math>v \in V \;</math> множество <math>\{ i \in I \; | \; v \in X_i \}</math> порождает связное поддерево T.




Древесная ширина графа, рис. 1. Граф и его древесная декомпозиция ширины 2
Альтернативное определение древесной ширины дается в терминах хордальных графов. Граф G = (V, E) является хордальным в том и столько том случае, если любой цикл длины не менее 4 содержит хорду, т.е. дугу между двумя непоследовательными вершинами цикла. Древесная ширина графа G не превышает значения k в том и только том случае, если G является подграфом хордального графа H, имеющего максимальную клику размером не более k.
 
 
Ширина древесной декомпозиции равна maxi2I jX | — 1, а древесная ширина графа G равна минимальной ширине древесной декомпозиции G.
 
 
Альтернативное определение дается в терминах хордальных графов. Граф G = (V, E) является хордальным в том и столько том случае, если любой цикл длины не менее 4 содержит хорду, т.е. дугу между двумя непоследовательными вершинами цикла. Древесная ширина графа G не превышает значения k в том и только том случае, если G является подграфом хордального графа H, имеющего максимальную клику размером не более k.




Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11653