Путевая ширина графа: различия между версиями

Перейти к навигации Перейти к поиску
Строка 72: Строка 72:




3. Найти Bk для значений k больше 3. Единственный структурный результат Bk заключается в том, что его планарные элементы являются либо самодвойственными, либо попарно двойственными. Это заключение следует из того факта, что двойственные планарные графы имеют одинаковую путевую ширину [29, 16].
3. Найти <math>\mathfrak{B}_k</math> для значений k больше 3. Единственный структурный результат <math>\mathfrak{B}_k</math> заключается в том, что его планарные элементы являются либо самодвойственными, либо попарно двойственными. Это заключение следует из того факта, что двойственные планарные графы имеют одинаковую путевую ширину [29, 16].




4. Найти точный алгоритм для вычисления путевой ширины сложности O*(2") (нотация O*() предполагает, что неэкспоненциальные члены классической нотации O() отбрасываются).
4. Найти точный алгоритм для вычисления путевой ширины сложности <math>O*(2^n) \, </math> (нотация O*() предполагает, что неэкспоненциальные члены классической нотации O() отбрасываются).




Источник — http://pco.iis.nsk.su/wega/index.php/Путевая_ширина_графа