4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 72: | Строка 72: | ||
3. Найти | 3. Найти <math>\mathfrak{B}_k</math> для значений k больше 3. Единственный структурный результат <math>\mathfrak{B}_k</math> заключается в том, что его планарные элементы являются либо самодвойственными, либо попарно двойственными. Это заключение следует из того факта, что двойственные планарные графы имеют одинаковую путевую ширину [29, 16]. | ||
4. Найти точный алгоритм для вычисления путевой ширины сложности O*(2 | 4. Найти точный алгоритм для вычисления путевой ширины сложности <math>O*(2^n) \, </math> (нотация O*() предполагает, что неэкспоненциальные члены классической нотации O() отбрасываются). | ||