Теория графов.Оргдеревья., Разбиение оргдеревьев. Опции

[Fanat]

Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.

[Michael_Rybak]

Идем от листов вверх к корню, и индексируем по ходу.

Лучше сразу на примере:



Берем листья: F, G, H, I, K, L, M, N. Присваиваем каждому из них индекс 0. Между собой соответствующие поддеревья изоморфны, и других таких нет.

Теперь рассматриваем узел, у которого все сыновья проиндексированы, а он - нет. Например E. Записываем индексы его сыновей: G(0), H(0); сортируем индексы: (0; 0). Смотрим, есть ли у нас такое поддерево среди рассмотренных? Нету. Значит, это - новое, даем ему индекс 1. Ведем такую табличку:

0: ()
1: (0; 0)

Берем следующий узел с проиндексированными сыновьями, например B. Записываем его детей: E(1), F(0); сортируем индексы: (0; 1). Такого еще не было, даем индекс 2:

0: ()
1: (0; 0)
2: (0; 1)

Дальше. Узел C. Дети: M(0), N(0). Сортируем индексы: (0; 0). Это у нас уже было. Это - индекс 1.

Узел J. Дети: K(0), L(0). Сортируем индексы: (0; 0). Это у нас уже было. Это - индекс 1.

Узел D. Дети: I(0), J(1). Сортируем индексы: (0; 1). Это у нас уже было. Это - индекс 2.

Узел А. Дети: B(2), C(1), D(2). Сортируем индексы: (1; 2; 2). Такого еще не было, это будет индекс 3:

0: ()
1: (0; 0)
2: (0; 1)
3: (1; 2; 2)

Таким образом, в дереве есть 4 вида неизоморфных поддеревьев, и корням изоморных поддеревьев поставлены в соответствие одинаковые индексы.

Чтобы делать это за n log n, можно строить префиксное дерево для списка полученных индексов (в котором, например, путь 1-2-2 оканчивается значением 3)

[Fanat]

Требуеться разбить на ВСЕ неизоморфные поддеревья.
Алгоритм:
Нахождение и удаление висячих вершин.
Проверка на изоморфность оргдеревьев.

Только вот с реализациеё чето у меня не особо. Даже списковое представление сделать не получаеться.