Теория графов.Оргдеревья., Разбиение оргдеревьев. |
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 |
И еще: "без циклов" = без ориентированных циклов? Или просто без циклов? Потому что если без ориентированных, от висячих вершин может и не оказаться Просто без циклов. В понимании препода оргдерева это оргдерево в обычном понимании.Только вот из корня не обязательно достижимы все вершины.Да и корня в принципе мы не знаем.Поэтому можем подвесить граф за любую вершину. Под поддеревом понимаеться любой граф. Алгоритм: как представляю себе я, подвесим граф за 1 вершину. Найдём висячии. Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл. Файлы сортируем по кол-ву вершин. И так далее. В конце необходимо подвесить за следующую вершину. (Очень долго =( ) Списковым представлением пользоваться не обязательно. Просто входные данные могут быть очень большими (около 10000 вершин , а то и больше),а это дастаточно экономный вариант хранения графа. Не откажусь от любой помощи. |
Текстовая версия | 24.04.2024 21:52 |