Теория графов.Оргдеревья., Разбиение оргдеревьев. |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Теория графов.Оргдеревья., Разбиение оргдеревьев. |
Fanat |
Сообщение
#1
|
Fanat Группа: Пользователи Сообщений: 261 Пол: Мужской Реальное имя: Сергей Репутация: 5 |
Как разбить ориентированное дерево на все неизоморфные поддеревья?..Входные данные-например,FO представление.
|
Маня |
Сообщение
#2
|
Группа: Пользователи Сообщений: 9 Пол: Женский Репутация: 1 |
Послушайте! А если я сделаю так?
Как всё это на паскаде организовать??? Задача: требуется определить изоморфны ли два ориентированных дерева или нет Входные данные : 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(т.е. произведение факториалов мощностей групп вершин) -------------------- Потому что, потому что
Всех нужнее и дороже, Всех доверчивей и строже В этом мире доброта В этом мире ДОБРОТА |
Текстовая версия | 20.04.2024 19:48 |