Сначала спросили по математике. Без ответов.
- Предположим, у меня есть плоский граф с плоским вложением, как мне найти разложение дерева?
- Каково оптимальное разложение дерева by- квадратной сетки? Не совсем уверен, как определить «оптимальный», но следует различать разложение с одним большим мешком и разложение с большим количеством больших мешков.
ds.algorithms
graph-theory
graph-algorithms
treewidth
integer-lattice
Ярослав Булатов
источник
источник
По первому вопросу открыто, можно ли найти разложение дерева для плоских графов за полиномиальное время. Алгоритм наилучшего приближения может быть алгоритмом RatCatcher Сеймура и Томаса, который вычисляет ширину ветви плоского графа, поэтому он имеет коэффициент аппроксимации 1,5 по соотношению между шириной ветви и шириной дерева.
Для второго мы имеем следующую теорему о ширинек × к сетки:
И сумки можно взять с размеромк + 1 с общим к ( к - 1 ) мешки. Я не уверен, что это то, что вы хотите, так что не стесняйтесь делать это, если вы измените определение «оптимальный».
источник
Если вам не нужна оптимальная декомпозиция дерева, вы можете построить декомпозицию дерева путем рекурсивного вычисления разделителей.
источник