4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы: количество зацеплений == Постановка задачи == Путевая ширина, …») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 2: | Строка 2: | ||
== Постановка задачи == | == Постановка задачи == | ||
Путевая ширина, наряду с более известной древесной шириной, является мерой «глобальной связности» графа. | Путевая ширина, наряду с более известной [[древесная ширина графа|древесной шириной]], является мерой «глобальной связности» графа. | ||
Пусть G – граф с n вершинами. Декомпозиция в форме ветвления применительно к графу G представляет собой пару (Г, т), где T – это дерево с вершинами, имеющими степень 1 или 3, а т – биекция множества листьев T на дуги G. Порядок дуги e в T, обозначаемый a(e), представляет собой число вершин v графа G, таких, что существуют листья t1; h m T в различных компонентах T(V(T); E(T) — e) с x{t\) и xfo), у которых v является конечной точкой. | Пусть G – граф с n вершинами. Декомпозиция в форме ветвления применительно к графу G представляет собой пару (Г, т), где T – это дерево с вершинами, имеющими степень 1 или 3, а т – биекция множества листьев T на дуги G. Порядок дуги e в T, обозначаемый a(e), представляет собой число вершин v графа G, таких, что существуют листья t1; h m T в различных компонентах T(V(T); E(T) — e) с x{t\) и xfo), у которых v является конечной точкой. | ||