древовидная декомпозиция графа

Question

Мне нужна начальная точка для реализации алгоритма в c для генерации tre-декомпозиции графа на входе.То, что я ищу, это алгоритм, чтобы сделать это.мне бы хотелось иметь псевдокод алгоритма, меня не волнует язык программирования, и меня не волнует сложность

В Интернете много теории, но на практике ничего нет.Я пытался понять, как сделать алгоритм, который может быть реализован в c.Но это сложно

Я пытался использовать следующую информацию:

• Алгоритм генерации разложения дерева

• https://math.mit.edu/~apost/courses/18.204-2016/18.204_Gerrod_Voigt_final_paper.pdf

и множество других информационных материалов.Но ничто из этой ссылки не было полезным.

Кто-нибудь может мне помочь?

Answer 1

Итак, вот алгоритм поиска узла в дереве.

1. Выбор произвольного узла v

2. Запуск DFS из vи установить размеры поддеревьев

3. Переместить в узел v (или начать с любого произвольного v, принадлежащего дереву)

4. Проверить математическоесостояние центроида для v

5. Если условие выполнено, вернуть текущий узел в виде центроида

6. В противном случае перейти к соседнему узлу с «наибольшим» размером поддерева,и вернемся к шагу 4

и алгоритму декомпозиции дерева

1. Сделать центроид в качестве корня нового дерева (которое мы назовемкак «дерево центроидов»)

2. Рекурсивно разлагать деревья в результирующем лесу

3. Сделать центроиды этих деревьев дочерними для центроидакоторый последний разделил их.

А вот пример кода.

https://www.geeksforgeeks.org/centroid-decomposition-of-tree/amp/