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

[Fanat]

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

[Маня]

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

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

Проиндексируем все листики,значит 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)....что-то сложновато получается....ЧТО делать?

[Michael_Rybak]

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

Если ребро идёт из листа к корню,то 1,если наоборот,то 2 ,если в обе стороны,то 3.

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

Чё-то слишком много получается, а чем дальше, тем хуже...

Согласен. А знаешь, почему? Потому что в том-то вся прелесть, что индексировать надо только то, что встретилось, а не все возможные комбинации. Например, ты говоришь: (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, потому что это - то же самое. Именно поэтому перед тем, как смотреть, что там у нас приклеено, надо отсортировать список приклееных пар (по возрастанию номера, например), т.е. установить канонический порядок их следования.