4551
правка
Путевая ширина графа: различия между версиями
Материал из WEGA
нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
Путевая ширина, наряду с более известной [[древесная ширина графа|древесной шириной]], является мерой «глобальной связности» графа. | Путевая ширина, наряду с более известной [[древесная ширина графа|древесной шириной]], является мерой «глобальной связности» графа. | ||
Пусть G – граф с n вершинами. Декомпозиция в форме ветвления применительно к графу G представляет собой пару ( | Пусть 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 имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой). | Ширина (Г, x) равна maxee£(r){a(e)} – иначе говоря, максимальному порядку среди всех дуг T. Путевой шириной G является минимальная ширина среди всех декомпозиций G в форме ветвления (в случае, если jE(G) j < 1, мы устанавливаем, что путевая ширина равна 0; если jE(G)j = 0, то G не допускает декомпозиции в форме ветвления; если jE(G)j = 1, то у G имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой). | ||
