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