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

[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-представлению мы можем найти концевые вершинки?