IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Теория графов.Оргдеревья., Разбиение оргдеревьев.
сообщение
Сообщение #1


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 9
Пол: Женский

Репутация: -  1  +


О!!! У меня родилась идея,точнее мысль nea.gif

Примеры графов в прикрепленных файлах.
Выходит,что у первого графа итог 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)

Прикрепленное изображение

Прикрепленное изображение


--------------------
Потому что, потому что
Всех нужнее и дороже,
Всех доверчивей и строже
В этом мире доброта
В этом мире ДОБРОТА
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Молодец что придумала пример smile.gif

Цитата
Теперь делаем то же самое с другим графом, причем табличку строим не заново, а продолжаем строить эту! Если они изоморфны, то в конце он тоже свернется в пару 3-4, соединенную ребром вида 3, и получит индекс 5.


Видишь? Не заново, а продолжаем строить эту!

Что касается реализации - на паскале я бы сначала слегка застрелился, а потом бы уже писал. STL все-таки страшно развращает. Ты на чем собралась писать?

Граф я храню FO представлением, но таким двойным: из каждой вершины помню все ребра, и входящие, и исходящие. Каждое ребро, таким образом, встречается 2 раза. При этом на каждом ребре ставлю отметку, какое оно (туда, обратно или в обе стороны).

Результат свертки для каждой вершины храню отдельной структурой (динамическим массивом, содержащим в порядке возрастания индексы приклееных вершин).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 9
Пол: Женский

Репутация: -  1  +


Значится так, вот как я поняла этот алгоритм: !low.gif

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 массива,как сравнивать я призабыла...к вечеру разберусь

Так вот... chore.gif

Ну как? Правильно ли я поняла? ypriamii.gif

Вот вопросик: 10.gif как по FO-представлению мы можем найти концевые вершинки? blink.gif


--------------------
Потому что, потому что
Всех нужнее и дороже,
Всех доверчивей и строже
В этом мире доброта
В этом мире ДОБРОТА
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Fanat   Теория графов.Оргдеревья.   4.11.2006 15:48
Michael_Rybak   Идем от листов вверх к корню, и индексируем по ход…   4.11.2006 16:45
Fanat   Требуеться разбить на ВСЕ неизоморфные поддеревья.…   6.11.2006 17:13
Michael_Rybak   Требуеться разбить на ВСЕ неизоморфные поддеревья…   6.11.2006 17:55
Fanat   Например,рассмотрим такое огрдерево. Дерево имее…   7.11.2006 1:00
Michael_Rybak   Приведи, пожалуйста, определения "FO представ…   7.11.2006 2:01
Fanat   Ориентированное дерево — это ориентированный граф …   7.11.2006 5:17
Michael_Rybak   Я сейчас выхожу, подумаю над задачей в дороге. А т…   7.11.2006 13:40
Michael_Rybak   И еще: "без циклов" = без ориентированны…   7.11.2006 18:47
Fanat   И еще: "без циклов" = без ориентированн…   7.11.2006 22:48
Michael_Rybak   Алгоритм: как представляю себе я, подвесим граф з…   8.11.2006 0:36
Fanat   Можешь на примере показать что мы храним в массива…   8.11.2006 1:40
Michael_Rybak   Можешь на примере показать что мы храним в массив…   8.11.2006 2:05
Fanat   Сколько думал, а сделать ничё не могу..... :blink:   14.11.2006 21:49
Michael_Rybak   Давай шаг за шагом. 1. Напиши программу, которая …   14.11.2006 22:58
Маня   Такая вот задача: требуется определить изоморфны л…   8.11.2006 4:15
Michael_Rybak   Прочти мой первый пост здесь. Алгоритм, который я…   8.11.2006 6:18
Маня   Послушайте! А если я сделаю так? Как всё это н…   16.11.2006 3:41
Michael_Rybak   Эвристики тут ни к чему. Сравнить два графа можно …   16.11.2006 4:49
Маня   Там все связано с разбиением деревьев на поддеревь…   17.11.2006 2:40
Michael_Rybak   Там *не все* связано с разибиением на поддеревья. …   17.11.2006 3:25
Маня   понимаешь,я уже несколько раз все твои сообщения п…   18.11.2006 23:30
Michael_Rybak   Давай разберемся с тем, что я называю индексацией.…   19.11.2006 6:01
Маня   Ой !!! Спасибо огромное! Знаешь,а…   20.11.2006 3:48
Michael_Rybak   Молодец, Маня, порадовала! :) Да, очень прав…   20.11.2006 6:17
Маня   :good: :good: :good: Просто СУПЕР!!…   23.11.2006 2:26
Маня   О!!! У меня родилась идея,точнее мысль…   23.11.2006 3:26
Michael_Rybak   Молодец что придумала пример :) Видишь? Не зано…   23.11.2006 8:33
Маня   Значится так, вот как я поняла этот алгоритм: :…   28.11.2006 15:26
Michael_Rybak   Схему ты описала правильно, но вот правильно ли ты…   28.11.2006 18:46


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 17:24
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name