Аноним

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

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


1) <math>\cup_{i \in I} X_{i} = V;</math>
:1) <math>\cup_{i \in I} X_{i} = V;</math>


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


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


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


<math>tw(G) \leq pw(G).</math>
::::::<math>tw(G) \leq pw(G).</math>


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


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


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


Графы с древесной шириной <math>k</math> известны также как частичные [[k-Дерево|<math>k</math>-деревья]].
Графы с древесной шириной <math>k</math> известны также как частичные [[k-Дерево|<math>k</math>-деревья]].
==Литература==
==Литература==
[WG'94]
* Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903.