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

Перейти к навигации Перейти к поиску
Нет описания правки
Строка 6: Строка 6:
Пусть G – граф с n вершинами. ''[[Декомпозиция]] в форме ветвления'' применительно к графу G представляет собой пару (Т, <math>\tau \, </math>), где T – это дерево с вершинами, имеющими степень 1 или 3, а <math>\tau \, </math> – [[биекция]] множества листьев T на дуги G. [[Порядок]] дуги e в T, обозначаемый <math>\alpha (e)\, </math>, представляет собой число вершин v графа G, таких, что существуют листья <math>t_1</math>, <math>t_2</math> дерева T в различных компонентах T(V(T), E(T) — e) с <math>\tau (t_1)\, </math> и <math>\tau (t_2)\, </math>, у которых v является конечной точкой.
Пусть G – граф с n вершинами. ''[[Декомпозиция]] в форме ветвления'' применительно к графу G представляет собой пару (Т, <math>\tau \, </math>), где T – это дерево с вершинами, имеющими степень 1 или 3, а <math>\tau \, </math> – [[биекция]] множества листьев T на дуги G. [[Порядок]] дуги e в T, обозначаемый <math>\alpha (e)\, </math>, представляет собой число вершин v графа G, таких, что существуют листья <math>t_1</math>, <math>t_2</math> дерева T в различных компонентах T(V(T), E(T) — e) с <math>\tau (t_1)\, </math> и <math>\tau (t_2)\, </math>, у которых v является конечной точкой.


Ширина (Г, x) равна maxee£(r){a(e)} – иначе говоря, максимальному порядку среди всех дуг T. Путевой шириной G является минимальная ширина среди всех декомпозиций G в форме ветвления (в случае, если jE(G) j < 1, мы устанавливаем, что путевая ширина равна 0; если jE(G)j = 0, то G не допускает декомпозиции в форме ветвления; если jE(G)j = 1, то у G имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой).
[[Ширина]] <math>(T, \tau )\, </math> равна <math>max_{e \in E(T)}</math>{<math>\alpha (e) \, </math>} – иначе говоря, максимальному порядку среди всех дуг T. ''Путевой шириной'' G является минимальная ширина среди всех декомпозиций G в форме ветвления (в случае, если <math>\mid E(G)\mid \le 1</math>, мы устанавливаем, что путевая ширина равна 0; если <math>\mid E(G)\mid = 0</math>, то G не допускает декомпозиции в форме ветвления; если <math>\mid E(G)\mid = 1</math>, то у G имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой).


Вышеприведенное определение может быть напрямую расширено на гиперграфы, в которых r представляет собой биекцию листьев T на гипердуги G. Это же определение можно так же легко распространить на матроиды.
Вышеприведенное определение может быть напрямую расширено на гиперграфы, в которых r представляет собой биекцию листьев T на гипердуги G. Это же определение можно так же легко распространить на матроиды.
Источник — http://pco.iis.nsk.su/wega/index.php/Путевая_ширина_графа