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

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

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

1075 байт убрано , 10 июля 2016

→‎Постановка задачи

Irina

4551

правка

@@ Строка 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.

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

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

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

Навигация

Поиск