Древесная ширина графа: различия между версиями
Glk (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Древесная ширина графа''' (''Treewidth of a graph'') | '''Древесная ширина графа''' (''[[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>G = (V,E)</math> ''древесной декомпозицией'' | подмножеств <math>V</math> и <math>T</math> — [[дерево]] с множеством [[вершина|вершин]] <math>I</math> и множеством [[ребро|ребер]] <math>F \subseteq I \times I</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>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> | :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>k</math>, справедливо включение <math>X_{i} \cap X_{k} \subseteq X_{j}</math>. | |||
''Шириной'' древесной декомпозиции называется <math>\max_{i \in | ''Шириной'' древесной декомпозиции называется <math>\max_{i \in I} |X_{i}| - 1</math>. ''Древесная ширина'' графа <math>G</math> определяется как наименьшая ширина древесной декомпозиции <math>G</math> и обозначается <math>tw(G)</math>. В частности, если в этом определении рассматривать не [[дерево|деревья]], а пути (точнее, [[цепь|цепи]]), то получим определение ''[[путевая ширина|путевой ширины]]'' <math>pw(G)</math>.Так как всякий путь есть дерево, то имеет место неравенство | ||
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 | :<math>tw(G) = \min \{\omega(H)| \; H\mbox{ есть хордальный граф и } G \subseteq H\} - 1</math>; | ||
\subseteq H\} - 1</math>; | |||
<math>pw(G) = \min \{\omega(H)| \; H\mbox{ есть интервальный граф и } G | :<math>pw(G) = \min \{\omega(H)| \; H\mbox{ есть интервальный граф и } G \subseteq H\} - 1</math>. | ||
\subseteq H\} - 1</math>. | |||
Графы с древесной шириной <math>k</math> известны также как частичные | Графы с древесной шириной <math>k</math> известны также как частичные [[k-Дерево|<math>k</math>-деревья]]. | ||
<math>k</math>-деревья. | |||
==Литература== | ==Литература== | ||
* Workshop. Herrsching, 1994 // Lect. Notes Comp. Sci., 1995, vol. 903. | |||
Текущая версия от 16:37, 7 февраля 2011
Древесная ширина графа (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.