Теория графов.Оргдеревья., Разбиение оргдеревьев. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Теория графов.Оргдеревья., Разбиение оргдеревьев. |
Fanat |
Сообщение
#1
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.
|
Маня |
Сообщение
#2
|
Группа: Пользователи Сообщений: 9 Пол: Женский Репутация: 1 |
О!!! У меня родилась идея,точнее мысль
Примеры графов в прикрепленных файлах. Выходит,что у первого графа итог 5- (3,4), соедин. 3, у второго 5-(3,4), соедин. 3,выходит,что они изоморфны, но даже по рисункам с первого взгляда видно, что они неизоморфны.Что это значит? Что способ неверен? или же мы проверяем не только конечный итог, но весь массив? Для первого это: 0-лист 1-(0,1) 2-(0,3) 3-(1,3) (2,2) 4-(2,1) 5-(3,4) Для второго: 0-лист 1-(0,1) 2-(0,3) 3-(1,3) 4-(2,2) 5-(3,4) -------------------- Потому что, потому что
Всех нужнее и дороже, Всех доверчивей и строже В этом мире доброта В этом мире ДОБРОТА |
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Молодец что придумала пример
Цитата Теперь делаем то же самое с другим графом, причем табличку строим не заново, а продолжаем строить эту! Если они изоморфны, то в конце он тоже свернется в пару 3-4, соединенную ребром вида 3, и получит индекс 5. Видишь? Не заново, а продолжаем строить эту! Что касается реализации - на паскале я бы сначала слегка застрелился, а потом бы уже писал. STL все-таки страшно развращает. Ты на чем собралась писать? Граф я храню FO представлением, но таким двойным: из каждой вершины помню все ребра, и входящие, и исходящие. Каждое ребро, таким образом, встречается 2 раза. При этом на каждом ребре ставлю отметку, какое оно (туда, обратно или в обе стороны). Результат свертки для каждой вершины храню отдельной структурой (динамическим массивом, содержащим в порядке возрастания индексы приклееных вершин). |
Маня |
Сообщение
#4
|
Группа: Пользователи Сообщений: 9 Пол: Женский Репутация: 1 |
Значится так, вот как я поняла этот алгоритм:
1. сравниваем кол-во вершин в обоих графах,если разное, то неизоморфны,иначе 2. находим концевые вершины 3. сравниваем кол-во концевых вершин в обоих графах, если разное, то неизоморфны,иначе 4. индексируем их,т.е. записываем в динамический массив данные о вершине, например vershina^[1].Name:='1'; vershina^[1].indeks:=0 5. смотрим,с какими вершинами соединены концевые вершины и рёберную связь между ними (если выходит - 1, входит - 2, двусторон. - 3) 6. запишем эту информацию просто в массив,который будет хранить значения индексов,значит у нас (0,1) - 1 7. сравниваем кол-во вершин,соедин. с концевыми вершинами в обоих графах,если разное, то неизоморфны,иначе 8. записываем эту информацию к вершинам vershina^[2].Name:='2'; vershina^[2].indeks:=1; В ИТОГЕ МЫ ПОЛУЧАЕМ ПРОЦЕДУРУ,СОСТОЯЩУЮ ИЗ 3-Х ПУНКТОВ,КОТОРУЮ НУЖНО ПРОКРУЧИВАТЬ В ЦИКЛЕ. 9. у нас получатся 2 динамических массива 10. начинаем сравнивать эти 2 массива,как сравнивать я призабыла...к вечеру разберусь Так вот... Ну как? Правильно ли я поняла? Вот вопросик: как по FO-представлению мы можем найти концевые вершинки? -------------------- Потому что, потому что
Всех нужнее и дороже, Всех доверчивей и строже В этом мире доброта В этом мире ДОБРОТА |
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Схему ты описала правильно, но вот правильно ли ты понимаешь центральное место - индексацию вершины - я не очень понял.
Мне кажется, тут нужен один большой динамический массив, каждый элемент которого - это набор пар (индекс-ребро), свернувшихся в некоторую вершину. Вот в нашей табличке: 0-лист 1-(0,1) 2-(0,3) 3-(1,3) (2,2) 4-(2,1) 5-(3,4) Каждая строка здесь - это элемент вот этого динамического массива. Типа такого: type TPair = record //структура для хранения одного "свернутого" объекта На каждой итерации ты все глубже залазишь в граф, сворачивая листы, появившиеся после предыдущей итерации. У каждой вершины на протяжении этого процесса хранится ее TBlock, в котором index пока что неивестен, а kids заполняется. Когда ты сворачиваешь лист, ты смотришь, к какой вершине он свернется, и вписываешь этот лист к блоку той вершины, в которую он свернется (вместе с типом ребра). Т.е. ты еще в начале объявляешь массив блоков: var b: array [1..n] of TBlock; В начале все блоки пусты. Когда вершина i сворачивается к вершине j, то в блок b[j] дописывается в поле kids пара TPair, в которой child_index - это индекс, присвоенный вершине i, а type_of_edge - тип ребра, соединяющего i и j. А когда j станет листом (т.е. все связанные с ней вершины, кроме одной, свернутся в нее), то в b[j].index мы запишем его индекс, полученный путем поиска b[j] в массиве a, т.е. в нашей табличке. Короче, Маня. Знаешь, с чего начни. Начни с того, что напиши программу, которая просто сворачивает граф. Т.е. на входе - ФО представление, на выходе что-то такое: Код Шаг 1 Листы: 1 2 5 9 В лист 1 свернулись: В лист 2 свернулись: В лист 5 свернулись: В лист 9 свернулись: Шаг 2 Листы: 3 4 7 В лист 3 свернулись: 1 2 В лист 4 свернулись: 9 В лист 7 свернулись: 5 Шаг 3 Листы 6 8 В лист 6 свернулись: 3 7 В лист 8 свернулись: 4 Итог: Граф свернулся в ребро, соединяющее вершины 6 и 8. Т.е. никакой индексации, просто свертка. Цитата как по FO-представлению мы можем найти концевые вершинки? Можно так. Заведи массив start[n], в котором в start[i] хранится начало списка достижимых из i вершин (в FO представлении). Например FO представление: 5 2 3 0 5 0 1 0 3 0 0 start[1] = 1 start[2] = 4 start[3] = 6 start[4] = 8 start[5] = 10 Теперь чтобы узнать, какие ребра идут из вершины x, мы идем по ФО прелставлению, начиная с позиции start[x], и пока не встретим 0. Чтобы узнать, какая вершина является листиком, надо посчитать, сколько несвернутых вершин с ней соединены. |
Текстовая версия | 4.05.2024 22:58 |