 Теория графов.Оргдеревья., Разбиение оргдеревьев. |
Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++
Прочтите прежде чем задавать вопрос!
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 |
И еще: "без циклов" = без ориентированных циклов? Или просто без циклов? Потому что если без ориентированных, от висячих вершин может и не оказаться
|
|
|
|
| Fanat |
Сообщение
#3
|
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Цитата(Michael_Rybak @ 7.11.2006 14:47)  И еще: "без циклов" = без ориентированных циклов? Или просто без циклов? Потому что если без ориентированных, от висячих вершин может и не оказаться Просто без циклов. В понимании препода оргдерева это оргдерево в обычном понимании.Только вот из корня не обязательно достижимы все вершины.Да и корня в принципе мы не знаем.Поэтому можем подвесить граф за любую вершину. Под поддеревом понимаеться любой граф. Алгоритм: как представляю себе я, подвесим граф за 1 вершину. Найдём висячии. Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл. Файлы сортируем по кол-ву вершин. И так далее. В конце необходимо подвесить за следующую вершину. (Очень долго =( ) Списковым представлением пользоваться не обязательно. Просто входные данные могут быть очень большими (около 10000 вершин , а то и больше),а это дастаточно экономный вариант хранения графа. Не откажусь от любой помощи. |
|
|
|
Сообщений в этой теме
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
Алгоритм: как представляю себе я, подвесим граф з… 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
|
Текстовая версия | 7.11.2025 11:14 |
Связь с администрацией: bu_gen в домене octagram.name