Теория графов.Оргдеревья., Разбиение оргдеревьев. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Теория графов.Оргдеревья., Разбиение оргдеревьев. |
Fanat |
Сообщение
#1
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.
|
Michael_Rybak |
Сообщение
#2
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Идем от листов вверх к корню, и индексируем по ходу.
Лучше сразу на примере: Берем листья: 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 |
Сообщение
#3
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Требуеться разбить на ВСЕ неизоморфные поддеревья.
Алгоритм: Нахождение и удаление висячих вершин. Проверка на изоморфность оргдеревьев. Только вот с реализациеё чето у меня не особо. Даже списковое представление сделать не получаеться. |
Текстовая версия | 26.04.2024 5:23 |