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

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

1) [math]\displaystyle{ \cup_{i \in I} X_{i} = V; }[/math]

2) для всех ребер [math]\displaystyle{ (v,w) \in E }[/math] существует [math]\displaystyle{ i \in I }[/math] такое, что [math]\displaystyle{ v \in X_{i} }[/math]и [math]\displaystyle{ w \in X_{i} }[/math]

3) для всех [math]\displaystyle{ i, j, k \in I }[/math] таких, что [math]\displaystyle{ j }[/math] лежит на пути в [math]\displaystyle{ T }[/math] из [math]\displaystyle{ i }[/math] в [math]\displaystyle{ k }[/math], справедливо включение [math]\displaystyle{ X_{i} \cap X_{k} \subseteq X_{j} }[/math].

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

[math]\displaystyle{ tw(G) \leq pw(G). }[/math]

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

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

[math]\displaystyle{ pw(G) = \min \{\omega(H)| \; H\mbox{ есть интервальный граф и } G \subseteq H\} - 1 }[/math].

Графы с древесной шириной [math]\displaystyle{ k }[/math] известны также как частичные [math]\displaystyle{ k }[/math]-деревья.

Литература

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