Древесная ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
== Постановка задачи == | == Постановка задачи == | ||
Древесная ширина графа определяется в терминах древесной декомпозиции. Древесная декомпозиция графа G = (V, E) | Древесная ширина графа определяется в терминах древесной декомпозиции. Древесная декомпозиция графа G = (V, E) представляет собой пару <math>( \{ X_i \; | \; i \in I \}, T = (I, F))</math>, где <math>\{ X_i \; | \; i \in I \}</math> – набор подмножеств V, называемых контейнерами, а T – дерево, такое, что | ||
• Для всех {v, w} | • <math>\bigcup_{i \in I} \; X_i = V</math> | ||
• Для всех v | |||
• Для всех <math>\{ v, w \} \in E</math> существует <math>i \in I \;</math>, такое, что <math>v, w \in X_i \;</math>. | |||
• Для всех <math>v \in V \;</math> множество <math>\{ i \in I \; | \; v \in X_i \}</math> порождает связное поддерево T. | |||
| Строка 47: | Строка 50: | ||
Входными данными задачи нахождения древесной ширины являются неориентированный граф G = (V, E), предположительно представленный в виде списка смежности, и целое положительное число k < |V|. Необходимо определить, верно ли, что древесная ширина графа G не превышает k, и в случае положительного ответа предложить древесную декомпозицию G с шириной не более k. | Входными данными задачи нахождения древесной ширины являются неориентированный граф G = (V, E), предположительно представленный в виде списка смежности, и целое положительное число k < |V|. Необходимо определить, верно ли, что древесная ширина графа G не превышает k, и в случае положительного ответа предложить древесную декомпозицию G с шириной не более k. | ||
== Основные результаты == | == Основные результаты == | ||