 Теория графов.Оргдеревья., Разбиение оргдеревьев. |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| Fanat |
 4.11.2006 11:48
Сообщение
#1
|
 Fanat  Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация:  5   |
Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.
|
   |
 
|
  |
Ответов
| Michael_Rybak |
7.11.2006 14:47
Сообщение
#2
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
И еще: "без циклов" = без ориентированных циклов? Или просто без циклов? Потому что если без ориентированных, от висячих вершин может и не оказаться
|
|
|
|
| Fanat |
7.11.2006 18:48
Сообщение
#3
|
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Цитата(Michael_Rybak @ 7.11.2006 14:47)  И еще: "без циклов" = без ориентированных циклов? Или просто без циклов? Потому что если без ориентированных, от висячих вершин может и не оказаться Просто без циклов. В понимании препода оргдерева это оргдерево в обычном понимании.Только вот из корня не обязательно достижимы все вершины.Да и корня в принципе мы не знаем.Поэтому можем подвесить граф за любую вершину. Под поддеревом понимаеться любой граф. Алгоритм: как представляю себе я, подвесим граф за 1 вершину. Найдём висячии. Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл. Файлы сортируем по кол-ву вершин. И так далее. В конце необходимо подвесить за следующую вершину. (Очень долго =( ) Списковым представлением пользоваться не обязательно. Просто входные данные могут быть очень большими (около 10000 вершин , а то и больше),а это дастаточно экономный вариант хранения графа. Не откажусь от любой помощи. |
|
|
|
Сообщений в этой теме
Fanat Теория графов.Оргдеревья. 4.11.2006 11:48
Michael_Rybak Идем от листов вверх к корню, и индексируем по ход... 4.11.2006 12:45
Fanat Требуеться разбить на ВСЕ неизоморфные поддеревья.... 6.11.2006 13:13 Michael_Rybak
Требуеться разбить на ВСЕ неизоморфные поддеревья... 6.11.2006 13:55 Fanat Например,рассмотрим такое огрдерево.
Дерево имее... 6.11.2006 21:00 Michael_Rybak Приведи, пожалуйста, определения "FO представ... 6.11.2006 22:01 Fanat Ориентированное дерево — это ориентированный граф ... 7.11.2006 1:17 Michael_Rybak Я сейчас выхожу, подумаю над задачей в дороге. А т... 7.11.2006 9:40 Michael_Rybak
Алгоритм: как представляю себе я, подвесим граф з... 7.11.2006 20:36 Fanat Можешь на примере показать что мы храним в массива... 7.11.2006 21:40 Michael_Rybak
Можешь на примере показать что мы храним в массив... 7.11.2006 22:05 Fanat Сколько думал, а сделать ничё не могу..... :blink: 14.11.2006 17:49 Michael_Rybak Давай шаг за шагом.
1. Напиши программу, которая ... 14.11.2006 18:58 Маня Такая вот задача:
требуется определить изоморфны л... 8.11.2006 0:15 Michael_Rybak Прочти мой первый пост здесь.
Алгоритм, который я... 8.11.2006 2:18 Маня Послушайте! А если я сделаю так?
Как всё это н... 15.11.2006 23:41 Michael_Rybak Эвристики тут ни к чему. Сравнить два графа можно ... 16.11.2006 0:49 Маня Там все связано с разбиением деревьев на поддеревь... 16.11.2006 22:40 Michael_Rybak Там *не все* связано с разибиением на поддеревья. ... 16.11.2006 23:25 Маня понимаешь,я уже несколько раз все твои сообщения п... 18.11.2006 19:30 Michael_Rybak Давай разберемся с тем, что я называю индексацией.... 19.11.2006 2:01 Маня Ой !!! Спасибо огромное!
Знаешь,а... 19.11.2006 23:48 Michael_Rybak Молодец, Маня, порадовала! :)
Да, очень прав... 20.11.2006 2:17 Маня :good: :good: :good:
Просто СУПЕР!!... 22.11.2006 22:26 Маня О!!! У меня родилась идея,точнее мысль... 22.11.2006 23:26 Michael_Rybak Молодец что придумала пример :)
Видишь? Не зано... 23.11.2006 4:33 Маня Значится так, вот как я поняла этот алгоритм: :... 28.11.2006 11:26 Michael_Rybak Схему ты описала правильно, но вот правильно ли ты... 28.11.2006 14:46 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 18.07.2025 14:12 |