Теория графов.Оргдеревья., Разбиение оргдеревьев. Опции

[Fanat]

Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.

[Маня]

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

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

[Michael_Rybak]

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

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

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

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

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

Результат свертки для каждой вершины храню отдельной структурой (динамическим массивом, содержащим в порядке возрастания индексы приклееных вершин).

[Маня]

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

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

Так вот...

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

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

[Michael_Rybak]

Схему ты описала правильно, но вот правильно ли ты понимаешь центральное место - индексацию вершины - я не очень понял.

Мне кажется, тут нужен один большой динамический массив, каждый элемент которого - это набор пар (индекс-ребро), свернувшихся в некоторую вершину.

Вот в нашей табличке:

0-лист
1-(0,1)
2-(0,3)
3-(1,3) (2,2)
4-(2,1)
5-(3,4)

Каждая строка здесь - это элемент вот этого динамического массива. Типа такого:

type TPair = record //структура для хранения одного "свернутого" объекта
  child_index: integer;
  type_of_edge: byte;
end;


type TBlock = record //структура для хранения одной строки нашей таблички
  index: integer;
  kids: Array of TPair
end;

var a: Array of TBlock; //массив, содержащий всю таблицу индексации.

На каждой итерации ты все глубже залазишь в граф, сворачивая листы, появившиеся после предыдущей итерации. У каждой вершины на протяжении этого процесса хранится ее TBlock, в котором index пока что неивестен, а kids заполняется. Когда ты сворачиваешь лист, ты смотришь, к какой вершине он свернется, и вписываешь этот лист к блоку той вершины, в которую он свернется (вместе с типом ребра).

Т.е. ты еще в начале объявляешь массив блоков:

var b: array [1..n] of TBlock;

В начале все блоки пусты. Когда вершина i сворачивается к вершине j, то в блок b[j] дописывается в поле kids пара TPair, в которой child_index - это индекс, присвоенный вершине i, а type_of_edge - тип ребра, соединяющего i и j.

А когда j станет листом (т.е. все связанные с ней вершины, кроме одной, свернутся в нее), то в b[j].index мы запишем его индекс, полученный путем поиска b[j] в массиве a, т.е. в нашей табличке.



Короче, Маня. Знаешь, с чего начни. Начни с того, что напиши программу, которая просто сворачивает граф. Т.е. на входе - ФО представление, на выходе что-то такое:

Код

Шаг 1
  Листы: 1 2 5 9
    В лист 1 свернулись:
    В лист 2 свернулись:
    В лист 5 свернулись:
    В лист 9 свернулись:
Шаг 2
  Листы: 3 4 7
    В лист 3 свернулись: 1 2
    В лист 4 свернулись: 9
    В лист 7 свернулись: 5
Шаг 3
  Листы 6 8
    В лист 6 свернулись: 3 7
    В лист 8 свернулись: 4
Итог:
  Граф свернулся в ребро, соединяющее вершины 6 и 8.

Т.е. никакой индексации, просто свертка.

как по FO-представлению мы можем найти концевые вершинки?

Можно так.
Заведи массив start[n], в котором в start[i] хранится начало списка достижимых из i вершин (в FO представлении).

Например

FO представление:

5
2 3 0 5 0 1 0 3 0 0

start[1] = 1
start[2] = 4
start[3] = 6
start[4] = 8
start[5] = 10

Теперь чтобы узнать, какие ребра идут из вершины x, мы идем по ФО прелставлению, начиная с позиции start[x], и пока не встретим 0.

Чтобы узнать, какая вершина является листиком, надо посчитать, сколько несвернутых вершин с ней соединены.