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