Теория графов.Оргдеревья., Разбиение оргдеревьев. |
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 вершин , а то и больше),а это дастаточно экономный вариант хранения графа. Не откажусь от любой помощи. |
Michael_Rybak |
Сообщение
#4
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Алгоритм: как представляю себе я, подвесим граф за 1 вершину. Найдём висячии. Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл. Файлы сортируем по кол-ву вершин. И так далее. В конце необходимо подвесить за следующую вершину. (Очень долго =( ) Я не понял, что ты имеешь ввиду под "Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл". Как именно мы это делаем? Сначала строим все возможные поддеревья, содержащие корень, а потом для каджой пары из них проверяем, не изоморфны ли они? Или как-то по ходу отсеиваем изоморфные? В общем вот что я тебе скажу. Лобовой алгоритм именно такой: подвесить за первую вершину, перебрать все возможные варианты последовательного отсечения части висячих вершин, получив таким образом все поддеревья, обязательно содержащие первую вершину. Потом подвесить за вторую вершину, и сделать то же самое. И так далее. Затем взять всю эту кучу поддеревьев, и попарно сравнивать их, находя изоморфные. Теперь, как это можно ускорить: 1) после того, как мы уже подвешивали за первую вершину, нам больше нет смысла рассматривать опять те поддеревья (но подвешенные за другую вершину), которым она принадлежит. Поэтому мы ее удаляем со всеми инцидентными ребрами. Подвешиваем за вторую, удаляем ее тоже, и т.д. 2) существенное ускорение можно получить неким подобием хеширования. Для каждого поддерева можно попридумывать несколько числовых характеристик, не зависящих от нумерации - количество вершин с нечетной степенью, количество ребер, соединяющих вершины одинаковой степени и т.п. И проверять на изоморфность только те пары поддеревьев, у которых все эти характеристики совпадают 3) можно воспользоваться приемом, который я тебе описал в самом первом посте. Подвесив за какую-нибудь вершину, будем вот так индексировать (систему индексирования нужно немного подправить, чтобы она учитывала направление ребра). Тогда можно будет значительную часть изоморфных поддеревьев отсечь на ходу. НО. Я очень сомневаюсь, что имеет смысл особо париться. Пункты 1 и 2, конечно, надо сделать, а вот пункт третий - с ним мороки побольше, а в худшем случае он все равно не поможет. Дело в том, что для некоторых входных данных количество неизоморфных поддеревьев будет порядка O(2^n), и никакие оптимизации тут не спасут при n = 10000, и даже при n = 50 Цитата Я так понял, что Списковым представлением пользоваться не обязательно. Просто входные данные могут быть очень большими (около 10000 вершин , а то и больше),а это дастаточно экономный вариант хранения графа. Еще меньше памяти занимает обычный список ребер. Вот: type TEdge = record x, y: longint end; Проходишь слева направо по FO представлению, и заполняешь edges в отсортированном порядке парами (откуда-куда). Отсортированном по "откуда", т.е. сначала идут все ребра, исходящие из 1, потом - из 2 и т.д (фактически, просто выбрасываешь нолики из FO). По ходу заполняешь first и last; first[i] - начало подсписка для вершины i, т.е. такое наименьшее t, что edges[t].x = i; а last[i] - конец подсписка для вершины i, т.е такое наименьшее w>t, что edges[w].x <> i. Теперь, чтобы пробежаться по вершинам, достижимым из i, надо пробежаться от edges[first[i]] до edges[last[i]-1]. Очень удобно и экономно. Поскольку здесь нам не помешают и обратные связи (от сына к отцу), ребра можно продублировать (a->b порождает b->a), отсортировать список, и уже потом пройтись по нему, заполняя first и last. Цитата Не откажусь от любой помощи. Пробуй, приходи, будем советоваться. Сообщение отредактировано: Michael_Rybak - |
Fanat |
Сообщение
#5
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Можешь на примере показать что мы храним в массивах first i last?..Почему просто не хранить список рёбер в двух массивах?..
|
Fanat |
Сообщение
#6
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Сколько думал, а сделать ничё не могу.....
|
Michael_Rybak |
Сообщение
#7
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Давай шаг за шагом.
1. Напиши программу, которая читает FO представление, и сохраняет информацию о ребрах так, чтобы можно было удобно бегать по ребрам, исходящим из данной вершины. Программа должна содержать процедуру PrintEdges(i: longint), печатающую ребра, входящие в вершину i, и ребра, исходящие из нее. Итак, на вход программа получает FO представление, на выходе - что-то типа такого: Код Вершина 1 Исходящие ребра: 1-2 1-3 1-6 Входящие ребра: 4-1 Вершина 2 Исходящие ребра: 2-3 Входящие ребра: 1-2 Вершина 3 Исходящие ребра: 3-5 3-6 Входящие ребра: 1-3 2-3 ... 2. Теперь напиши программу, которая выдаст список *всех* возможных поддеревьев данного графа. Делаем это так. Упорядочим все ребра (пронумеруем). Сначала построим список всех поддеревьев, содержащих 0 ребер. Т.е. просто берем все вершины, каждую из них обзываем поддеревом. Теперь построим все поддеревья, использующие только первое ребро. Для этого надо попытаться к каждому из его концов прикрепить одно из уже построеных поддеревьев. Теперь построим все поддеревья, использующие только первых два ребра (но не обязательно оба). Для этого надо попытаться к каждому из концов второго ребра прикрепить одно из уже построеных поддеревьев. Теперь построим все поддеревья, использующие только первых три ребра (но не обязательно каждое). Для этого надо попытаться к каждому из концов третьего ребра прикрепить одно из уже построеных поддеревьев. И так далее. Давай на твоем примере. FO = 4240020 Пронумеруем ребра (как угодно) Ребро 1: 1->2 Ребро 2: 3->2 Ребро 3: 1->4 Поддеревья будем описывать так: [(список_вершин), (список_ребер)] Поддеревья, содержащие 0 ребер: {[(1), ()], [(2), ()], [(3), ()], [(4), ()]} Теперь попробуем использовать ребро 1, т.е. ребро 1->2. Нам надо из уже построенного списка поддеревьев {[(1), ()], [(2), ()], [(3), ()], [(4), ()]} присоединить что-то к 1, а что-то к 2. В данном случае единственный результат - это [(1, 2), (1->2)]. Получили список подграфов, в котором используется только первое ребро: {[(1), ()], [(2), ()], [(3), ()], [(4), ()], [(1, 2), (1->2)]} Следующее ребро: 3->2. Пробуем присоединить. К тройке можно присоединить только [(3), ()], а к двойке - либо [(2), ()], либо [(1, 2), (1->2)]. Получаем еще два новых поддерева: [(2, 3), (3->2)] и [(1, 2, 3), (1->2, 3->2)]. Общий список: {[(1), ()], [(2), ()], [(3), ()], [(4), ()], [(1, 2), (1->2)], [(2, 3), (3->2)], [(1, 2, 3), (1->2, 3->2)]} И последнее ребро: 1->4. К четверке можно присоединить только [(4), ()], а к единице уже кучу всего: [(1), ()], [(1, 2), (1->2)], [(1, 2, 3), (1->2, 3->2)]. Получаем новых 3 поддерева. Общий список выглядит так: {[(1), ()], [(2), ()], [(3), ()], [(4), ()], [(1, 2), (1->2)], [(2, 3), (3->2)], [(1, 2, 3), (1->2, 3->2)], [(1, 4), (1->4)], [(1, 2, 4), (1->2, 1->4)], [(1, 2, 3, 4), (1->2, 3->2, 1->4)]} Вот мы и построили все связные подграфы. В общем случае, пытаясь использовать новое ребро x->y, мы бежим по списку уже построенных поддеревьев, и выбираем содержащие вершину x; пусть нашлось n вариантов. Потом бежим еще раз, и выбираем содержащие вершину y; пусть нашлось m вариантов. Тогда для каждого из n вариантов пробуем каждый из m вариантов, и получаем nm вариантов использования нового ребра. Что не понятно, спрашивай. |
Текстовая версия | 27.04.2024 5:06 |