Древесная ширина графа

Материал из WikiGrapp
Перейти к:навигация, поиск

Древесная ширина графа (Treewidth of a graph) — для заданного графа G = (V,E) древесной декомпозицией называется пара (\{X_{i}| \, i \in I\}, T = (I,F)), где \{X_{i} | \, i \in I\} — семейство подмножеств V и Tдерево с множеством вершин I и множеством ребер F \subseteq I \times I такими, что

1) \cup_{i \in I} X_{i} = V;
2) для всех ребер (v,w) \in E существует i \in I такое, что v \in
X_{i}и w \in X_{i}
3) для всех i, j, k \in I таких, что j лежит на пути в T из i в k, справедливо включение X_{i} \cap X_{k} \subseteq X_{j}.

Шириной древесной декомпозиции называется \max_{i \in I} |X_{i}| - 1. Древесная ширина графа G определяется как наименьшая ширина древесной декомпозиции G и обозначается tw(G). В частности, если в этом определении рассматривать не деревья, а пути (точнее, цепи), то получим определение путевой ширины pw(G).Так как всякий путь есть дерево, то имеет место неравенство

tw(G) \leq pw(G).

Древесная ширина (и соответственно путевая ширина) графа G связана с кликовым числом \omega(G) наименьшего хордального (соответственно интервального) графа, в который рассматриваемый граф G может быть вложен, следующим образом:

tw(G) = \min \{\omega(H)| \; H\mbox{ есть хордальный граф и } G \subseteq H\} - 1;
pw(G) = \min \{\omega(H)| \; H\mbox{ есть интервальный граф и } G \subseteq H\} - 1.

Графы с древесной шириной k известны также как частичные k-деревья.

Литература

  • Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.