4446
правок
Путевая ширина графа: различия между версиями
Материал из WEGA
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
Путевая ширина, наряду с более известной [[древесная ширина графа|древесной шириной]], является мерой «глобальной связности» графа. | Путевая ширина, наряду с более известной [[древесная ширина графа|древесной шириной]], является мерой «глобальной связности» графа. | ||
Пусть G – граф с n вершинами. ''[[Декомпозиция]] в форме ветвления'' применительно к графу G представляет собой пару | Пусть G – граф с n вершинами. ''[[Декомпозиция]] в форме ветвления'' применительно к графу G представляет собой пару <math>(T, \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 имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой). | [[Ширина]] <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 имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой). | ||
