4446
правок
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 29: | Строка 29: | ||
Известно, что большое число теоретико-графовых задач может быть решено за линейное время в случае, если их входные данные ограничены графами небольшой (иначе говоря, фиксированной) древесной или путевой ширины [2]. | Известно, что большое число теоретико-графовых задач может быть решено за линейное время в случае, если их входные данные ограничены графами небольшой (иначе говоря, фиксированной) древесной или путевой ширины [2]. | ||
[[Файл:Treewidth.png]] | |||
Путевая ширина графа | Рис. 1. Путевая ширина графа | ||
Пример графа и его декомпозиция в форме ветвления с путевой шириной 3 | Пример графа и его декомпозиция в форме ветвления с путевой шириной 3 | ||