4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 8: | Строка 8: | ||
[[Ширина]] <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 имеется декомпозиция в форме ветвления, состоящая из дерева с одной вершиной – ширина этой декомпозиции считается нулевой). | ||
Вышеприведенное определение может быть напрямую расширено на гиперграфы, в которых | Вышеприведенное определение может быть напрямую расширено на [[гиперграф|гиперграфы]], в которых <math>\tau \, </math> представляет собой биекцию листьев T на гипердуги G. Это же определение можно так же легко распространить на [[матроид|матроиды]]. | ||
Определение путевой ширины было введено Робертсоном и Сеймуром [25]; оно служило основным инструментом при доказательстве гипотезы Вагнера в их серии работ по минорам графов. Оно использовалось в качестве альтернативы понятию древесной ширины, поскольку оказалось более удобным для обращения в контексте этого доказательства. Отношение между путевой шириной и древесной шириной задается следующим образом. | Определение путевой ширины было введено Робертсоном и Сеймуром [25]; оно служило основным инструментом при доказательстве гипотезы Вагнера в их серии работ по минорам графов. Оно использовалось в качестве альтернативы понятию древесной ширины, поскольку оказалось более удобным для обращения в контексте этого доказательства. Отношение между путевой шириной и древесной шириной задается следующим образом. | ||
Теорема ([25]) Если G представляет собой граф, тогда branchwidth(G) | '''Теорема 1''' ([25]) | ||
'''Если G представляет собой граф, тогда <math>branchwidth(G) \le treewidth(G) + 1 \le \mathcal{b} 3/2 branchwidth(G)\mathcal{c} </math>, где branchwidth(G) – путевая ширина графа G, а treewidth(G) – его древесная ширина.''' | |||
С понятием путевой ширины связаны алгоритмические задачи двух типов: нахождение быстрых алгоритмов, вычисляющих ее значение, и использование ее для разработки быстрых алгоритмов динамического программирования для решения других задач. | С понятием путевой ширины связаны алгоритмические задачи двух типов: нахождение быстрых алгоритмов, вычисляющих ее значение, и использование ее для разработки быстрых алгоритмов динамического программирования для решения других задач. | ||