4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 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 является конечной точкой. | ||
Ширина ( | [[Ширина]] <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. Это же определение можно так же легко распространить на матроиды. | ||