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

[Fanat]

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

[Маня]

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


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

Входные данные : 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(т.е. произведение факториалов мощностей групп вершин)

[Michael_Rybak]

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