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

[Fanat]

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

[Маня]

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

[Michael_Rybak]

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

[Маня]

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

[Michael_Rybak]

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

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

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

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

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

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

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

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