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

Идем от листов вверх к корню, и индексируем по ходу.

Лучше сразу на примере:



Берем листья: F, G, H, I, K, L, M, N. Присваиваем каждому из них индекс 0. Между собой соответствующие поддеревья изоморфны, и других таких нет.

Теперь рассматриваем узел, у которого все сыновья проиндексированы, а он - нет. Например E. Записываем индексы его сыновей: G(0), H(0); сортируем индексы: (0; 0). Смотрим, есть ли у нас такое поддерево среди рассмотренных? Нету. Значит, это - новое, даем ему индекс 1. Ведем такую табличку:

0: ()
1: (0; 0)

Берем следующий узел с проиндексированными сыновьями, например B. Записываем его детей: E(1), F(0); сортируем индексы: (0; 1). Такого еще не было, даем индекс 2:

0: ()
1: (0; 0)
2: (0; 1)

Дальше. Узел C. Дети: M(0), N(0). Сортируем индексы: (0; 0). Это у нас уже было. Это - индекс 1.

Узел J. Дети: K(0), L(0). Сортируем индексы: (0; 0). Это у нас уже было. Это - индекс 1.

Узел D. Дети: I(0), J(1). Сортируем индексы: (0; 1). Это у нас уже было. Это - индекс 2.

Узел А. Дети: B(2), C(1), D(2). Сортируем индексы: (1; 2; 2). Такого еще не было, это будет индекс 3:

0: ()
1: (0; 0)
2: (0; 1)
3: (1; 2; 2)

Таким образом, в дереве есть 4 вида неизоморфных поддеревьев, и корням изоморных поддеревьев поставлены в соответствие одинаковые индексы.

Чтобы делать это за n log n, можно строить префиксное дерево для списка полученных индексов (в котором, например, путь 1-2-2 оканчивается значением 3)

Требуеться разбить на ВСЕ неизоморфные поддеревья.
Алгоритм:
Нахождение и удаление висячих вершин.
Проверка на изоморфность оргдеревьев.

Только вот с реализациеё чето у меня не особо. Даже списковое представление сделать не получаеться.

А я и написал тебе, как разбить на ВСЕ неизоморфные поддеревья.

А если нет - тогда потрудись объяснить, что значит "разбить", и приведи пример входа и выхода для требуемого алгоритма. И лучше - несколько примеров.

Например,рассмотрим такое огрдерево.
Нажмите для просмотра прикрепленного файла

Дерево имеет 4 неизоморфных поддерева.
Приведено их FO представление.



В этом коде создаем списковое представление дерева.Просьба подправить, так как оно создаётся неверно.
Что-то со ссылками.Напиример в рассмотреном нами дереве результат будет 1 4 268 вместо должного 1 2 4.

Приведи, пожалуйста, определения "FO представление" и "ориентированное дерево"

Ориентированное дерево — это ориентированный граф без циклов.(Так это понимает наш препод).

Массив FO формируется следующим образом: сначала записывается число вершин орграфа,затем номера вершин в любом порядке в которые заходят дуги из первой вершины,затем ставится разделитель 0.Далее записываются номера вершин, в которые заходят дуги из второй вершины,после чего ставиться разделитель и т.д.

Я сейчас выхожу, подумаю над задачей в дороге. А ты пока напиши:

1) под поддеревом понимается любой подграф?
2) подробнее об предложенном преподом алгоритме. Что значит "удаление и сравнение".
3) тебе обязательно пользоваться именно списковым представлением? Если нет, я тебе напишу, как это намного проще реализовать

И еще: "без циклов" = без ориентированных циклов? Или просто без циклов? Потому что если без ориентированных, от висячих вершин может и не оказаться

Просто без циклов.
В понимании препода оргдерева это оргдерево в обычном понимании.Только вот из корня не обязательно достижимы все вершины.Да и корня в принципе мы не знаем.Поэтому можем подвесить граф за любую вершину.


Под поддеревом понимаеться любой граф.
Алгоритм: как представляю себе я, подвесим граф за 1 вершину. Найдём висячии. Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл. Файлы сортируем по кол-ву вершин. И так далее. В конце необходимо подвесить за следующую вершину. (Очень долго =( )

Списковым представлением пользоваться не обязательно. Просто входные данные могут быть очень большими (около 10000 вершин , а то и больше),а это дастаточно экономный вариант хранения графа.

Не откажусь от любой помощи.

Я не понял, что ты имеешь ввиду под "Рассмотрим всевозможные комбинации удаляя их и проверяя на изоморфность и неизоморфные запишем в файл". Как именно мы это делаем? Сначала строим все возможные поддеревья, содержащие корень, а потом для каджой пары из них проверяем, не изоморфны ли они? Или как-то по ходу отсеиваем изоморфные?

В общем вот что я тебе скажу. Лобовой алгоритм именно такой: подвесить за первую вершину, перебрать все возможные варианты последовательного отсечения части висячих вершин, получив таким образом все поддеревья, обязательно содержащие первую вершину. Потом подвесить за вторую вершину, и сделать то же самое. И так далее.

Затем взять всю эту кучу поддеревьев, и попарно сравнивать их, находя изоморфные.

Теперь, как это можно ускорить:

1) после того, как мы уже подвешивали за первую вершину, нам больше нет смысла рассматривать опять те поддеревья (но подвешенные за другую вершину), которым она принадлежит. Поэтому мы ее удаляем со всеми инцидентными ребрами. Подвешиваем за вторую, удаляем ее тоже, и т.д.

2) существенное ускорение можно получить неким подобием хеширования. Для каждого поддерева можно попридумывать несколько числовых характеристик, не зависящих от нумерации - количество вершин с нечетной степенью, количество ребер, соединяющих вершины одинаковой степени и т.п. И проверять на изоморфность только те пары поддеревьев, у которых все эти характеристики совпадают

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

НО.

Я очень сомневаюсь, что имеет смысл особо париться. Пункты 1 и 2, конечно, надо сделать, а вот пункт третий - с ним мороки побольше, а в худшем случае он все равно не поможет.

Дело в том, что для некоторых входных данных количество неизоморфных поддеревьев будет порядка O(2^n), и никакие оптимизации тут не спасут при n = 10000, и даже при n = 50



Еще меньше памяти занимает обычный список ребер. Вот:

type TEdge = record x, y: longint end;

var edges: array[1 .. MAX_E] of TEdge;
    first: array[1 .. MAX_N] of longint;
    last: array[1 .. MAX_N] of longint;

Проходишь слева направо по 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.



Пробуй, приходи, будем советоваться.

Можешь на примере показать что мы храним в массивах first i last?..Почему просто не хранить список рёбер в двух массивах?..

Для твоего примера: FO представление: 4240020

Массив edges:

{(1, 2), (1, 4), (3, 2)}

Массив first: {1, -1, 3, -1}
Массив last: {3, -1, 4, -1}

first[1] = 1, last[1] = 3; это значит, что ребра, исходящие из вершины 1, начинаются в edges[1], и кончаются в edges[3] (не включительно)

first[2] = -1, last[2] = -1; это значит, что ребер, исходящих из вершины 2, нет

first[3] = 3, last[3] = 4; это значит, что ребра, исходящие из вершины 3, начинаются в edges[3], и кончаются в edges[4] (не включительно)

first[4] = -1, last[4] = -1; это значит, что ребер, исходящих из вершины 4, нет

Фактически, first и last - это указатели на начало и конец подсписка ребер для данной вершины.

Теперь, чтобы пробежаться по ребрам, исходящим из вершины i, пишем:

Writeln('Список вершин, достижимых по ребру из ', i, ':');
for t := first[i] to last[i] - 1 do
  Writeln(edges[t].y);

Что значит список ребер в двух массивах? Как это?

Хранить можно как угодно; я всегда пользуюсь именно таким представлением, которое описал. Убедился, что так - удобнее всего, по крайней мере для меня.

Такая вот задача:
требуется определить изоморфны ли два ориентированных дерева или нет.

Входные данные: я задаю два уже ориентированных дерева в FO-представлении.

Помогите,пожалуйста,(сравнить) определить алгоритм изоморфизма этих графов!

М

Темы объединены. Чтобы не дублировать информацию из одной в другую, т.к. они очень похожи... volvo

Прочти мой первый пост здесь.

Алгоритм, который я там описываю, очень похож на то, что тебе нужно.

Сначала придумай, как его переделать для проверки двух ациклических *неориентированных* графов на изоморфность.

Потом придумай, как сравнивать ориентированные деревья.

Сколько думал, а сделать ничё не могу.....

Давай шаг за шагом.

1. Напиши программу, которая читает FO представление, и сохраняет информацию о ребрах так, чтобы можно было удобно бегать по ребрам, исходящим из данной вершины. Программа должна содержать процедуру PrintEdges(i: longint), печатающую ребра, входящие в вершину i, и ребра, исходящие из нее.

Итак, на вход программа получает FO представление, на выходе - что-то типа такого:



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 вариантов использования нового ребра.


Что не понятно, спрашивай.

Послушайте! А если я сделаю так?
Как всё это на паскаде организовать???


Задача: требуется определить изоморфны ли два ориентированных дерева или нет

Входные данные : FO-представление графа

Выходные данные:
либо ориентированные деревья изоморфны/не изоморфны
либо граф не является ориентированным (неправильно заданы входные данные)

Алгоритм:

Будем обозначать направленное ребро через единичку, находящуюся на пересечении двух вершин в матрице смежности. Причём если стрелка ребра направлена только в одну сторону, то ставим единичку на пересечении вершины, откуда она отходит, с вершиной, куда она входит.

Т.к. по определению дерево, это, грубо сказать, связный граф без циклов, то будем воспринимать двунаправленное ребро, за простое ребро.


Пример.







Матрица смежности:
0100000
1001000
0001000
0010100
0001010
0000101
0000000



1. С помощью матрицы смежности делаем проверку на правильность ввода, т.е. проверяем:
 является ли граф связным
 не имеет ли он циклов.
3. Очевидно, что деревья с разным количеством вершин не могут быть изоморфны, следовательно, делаем проверку (создаём процедуру) на одинаковое количество вершин в двух входных ориентированных графах.
4.Фактически, графы будут изоморфны тогда и только тогда, когда из матрицы смежности одного графа можно получить матрицу смежности другого графа перестановкой (перенумерацией) вершин.
Т.е. для нашего примера:
1234567
1 0100000
2 1001000
3 0001000
4 0010100
5 0001010
6 0000101
7 0000000
Получим
1435672
1 0000001
4 0011000
3 0100000
5 0100100
6 0001010
7 0000000
2 1100000
Т.е. два ориентированных дерева G1 и G2 изоморфны

G1 G2
Причём G2 получен путём перестановок вершин в матрице смежности.

Таким образом, если мы имеем два графа (с одинаковым количеством вершин), заданных матрицами инцидентности. Достаточно перебрать все возможные перестановки вершин второго графа (разумеется, при каждой перестановке соответствующим способом меняя матрицу) - если ни в одном случае матрицы не совпадут - значит графы неизоморфны.


Оптимизация:
Поскольку сравнивать придётся матрицы n*n, (где n-количество вершин), а всего перестановок n!, то разумно будет сократить количество тех перестановок, которые имеют смысл.

Возьмём граф и разобьем его вершины на группы по парам (In,Out), где In - количество входящих рёбер,т.е. количество единиц в соответствующем столбце, а Out – количество исходящих рёбер, т.е. количество единиц в соответствующей строке.

Для указанного примера, имеем:
1 (1,1)
2 (1,2)
3 (1,1)
4 (3,2)
5 (2,2)
6 (1,2)
7 (1,1)

Получаем 4 группы вершин: {1,3,7}{2,6}{4}{5}
Так вот, вместо 7! = 1*2*3*4*5*6*7 = 5040 перестановок достаточно просто отсортировать вершины в обоих графах по соответствующим парам (например, сначала по In, потом по Out) и разумных перестановок будет только 3!*2!*1!*1!=1*1*1*2*3*1*2=12(т.е. произведение факториалов мощностей групп вершин)

Эвристики тут ни к чему. Сравнить два графа можно *всегда* очень быстро, за полиномиальное время. Никаких n!. Читай мой пост и задавай вопросы.

Там все связано с разбиением деревьев на поддеревья...а мне это не нужно!

Там *не все* связано с разибиением на поддеревья. Просто проиндескируй оба дерева, и посмотри, равны ли индексы. Если ты потратишь хоть немного времени и разберешься в том, что я написал, ты поймешь, что это именно то, что тебе нужно.

понимаешь,я уже несколько раз все твои сообщения прочитала,но толком ничего не поняла...
Во-первых как по матрице смежности мы будем находить корневую или концевые вершины?
Во-вторых, а если корневых вершин две?
Я поняла,что надо взять концевые вершины,проиндексировать их через (0)
Потом как мы достаиваем ребро? Всё...голова кругом... Эта курсовая меня в сумашедший дом загонит...Так,значит достаиваем ребро и как-то что-то индексируем (0,1)...а как же проверять изоморфность?

Давай разберемся с тем, что я называю индексацией. Индексация - это присвоение индексов (номеров) поддеревьям так, чтобы изоморфным поддеревьям соответствовали одинаковые индексы, а не изоморфным - разные.

В случае графа "без корня" это делается путем сворачивания листьев в каждом из двух графов.

Смотри. Пусть у нас есть графы А и В. На первом шагу ничего еще не свернули. Считаем, сколько листьев в А и в В. Если количества листьев - разные, то уже понятно, что графы неизоморфны.

Иначе говорим, что все листы получают индекс 0.

Теперь сворачиваем все листы. Сворачиваем - это значит "приклеиваем" индекс листа к той вершине, к которой ведет единственное ребро из этого листа, а сам лист удаляем вместе с этим ребром. Например, если какая-то вершина была соединена с двумя листьями и тремя не-листьями, то те два листа (с их индексами 0) мы приклеим к ней, а три других ребра останутся.

Теперь в каждом графе появились новые листья (благодаря сворачиванию листьев на предыдущем шаге). Листьев опять должно быть поровну (если нет - сразу не изоморфны). Но теперь этого уже не достаточно. Кроме того, что листьев должно быть поровну, листья должны быть еще и попарно равными. А именно: к некоторым листьям "приклеился" один лист на прошлом этапе, к некоторым - больше. Такие "свертыши" нужно отличать друг от друга. Вот здесь и начинается индексация. Берем любой лист-"свертыш". Смотрим, что к нему там приклеено, т.е. записываем индексы приклееных к нему листьев, например (0; 0; 0). Сортируем их (индексы) по возрастанию, и даем ему индекс 1. Теперь, если мы встретим когда-либо еще один лист-свертыш, к которому было приклеено (0; 0; 0), это будет означать, что он изоморфен этому, и ему мы тоже дадим индекс 1.

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

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

Ой !!! Спасибо огромное!

Знаешь,а у меня задание изоморфизм ОРИЕНТИРОВАННЫХ деревьев.
Пример, есть такое дерево:оно в добавленных файлах.

Проиндексируем все листики,значит 1(0),4(0),8(0).Будем смотреть как связаны вершины. Если ребро идёт из листа к корню,то 1,если наоборот,то 2 ,если в обе стороны,то 3. Получаем -
2(0,1), 3(0,3), 7 (0,3). Теперь (0,1)-4,(0,2)-5, (0,3)-6. Получаем - 2(4),3(6),7(6). Дальше (1,4)-7,(1,5)-8,(1,6)-9,(2,4)-10,...,(3,6)-15...Чё-то слишком много получается, а чем дальше, тем хуже...5(12,13)....что-то сложновато получается....ЧТО делать?

Молодец, Маня, порадовала!


Да, очень правильная мысль.


Согласен. А знаешь, почему? Потому что в том-то вся прелесть, что индексировать надо только то, что встретилось, а не все возможные комбинации. Например, ты говоришь: (0,1)-4,(0,2)-5, (0,3)-6. А зачем тебе (0,2)-5, если такого в графе нету?

Поправляем твои рассуждения с этой точки зрения.

Проиндексируем все листики, значит 1(0),4(0),8(0).
Будем смотреть как связаны вершины. Если ребро идёт из листа к корню,то 1,если наоборот,то 2 ,если в обе стороны,то 3.

Сворачиваем. Листьями становятся вершины 2, 3 и 7. У двойки приклеено (0,1). Даем вершине, к которой приклеено (0,1), следующий неиспользованный индекс, т.е. 1. У тройки приклеено (0,3). Даем вершине, к которой приклеено (0,3), следующий неиспользованный индекс, т.е. 2. У семерки приклеено (0,3). Даем вершине, к которой приклеено (0,3), следующий неиспользованный индекс, СТОП! Это мы уже делали - вершина, к которой приклеено (0,3) уже имеет индекс 2. Получаем - 2(1), 3(2), 7(2).

На следующем этапе листьями становятся 5 и 6. К пятерке приклеено (1,3) и (2,2). Вершине, к которой приклеено (1,3) и (2,2), дадим следующий неиспользованный индекс, т.е. 3. К шестерке приклеено (2,1). Вершине, к которой приклеено (2,1), дадим индекс 4. Получаем - 5(3), 6(4).

Процесс свертки заканчивается, когда всё свернется либо в одну точку, либо в две (как в нашем случае). Теперь всему графу ставим в соответствие новый индекс: "Графу, свернувшемуся в пару 3 и 4 (помним, что это - индексы пятерки и шестерки соответственно), соединенную ребром вида 3, ставим в соответствие следующий неиспользованный индекс, т.е. 5".

Вышла такая табличка:

0 - лист
1 - (0,1)
2 - (0,3)
3 - (1,3) и (2,2)
4 - (2,1)
5 - граф, свернувшийся в пару 3-4, соединенную ребром вида 3

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

Еще важная деталь: если у нас встретится вершина, к которой приклеено (1,3) и (2,2), мы ей дадим индекс 3, т.к. это уже было. Но если у нас встретится вершина, к которой приклеено (2,2) и (1,3), мы должны ей тоже дать индекс 3, потому что это - то же самое. Именно поэтому перед тем, как смотреть, что там у нас приклеено, надо отсортировать список приклееных пар (по возрастанию номера, например), т.е. установить канонический порядок их следования.

Просто СУПЕР!!! ВСЁ поняла!

но,естественно, возникли другие проблемы....как ты,например,посоветуешь ввести данные,т.е. через матрицу смежности или 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)

Нажмите для просмотра прикрепленного файла

Нажмите для просмотра прикрепленного файла

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



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

Что касается реализации - на паскале я бы сначала слегка застрелился, а потом бы уже писал. 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-представлению мы можем найти концевые вершинки?

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

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

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

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, т.е. в нашей табличке.



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



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



Можно так.
Заведи массив 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.

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