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

Древесная ширина графа (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.