Изоморфизм - штука сильная +)

Да простят модераторы за спам... Народ... Я тут все в Web да в Web. Тут задачку в инсте дали, написать на Pascal програмку, которая проверяет - являются ли 2 графи изоморфными или нет. Если у кого есть ссылка или кто знает как что-то подобное делать - давайте с радостью. Еще хочется посомтреть на алгоритм работы (ну это уже если модератор решит переместить - пусть перемещает тему в "Алгоритмы"). Данные я как хотел вводить - число вершин первого, число вершин второго. А потом - заполнять двумерный массив n*n символами 1 или 0. 1 - если присутствует путь и 0 - если нет. Графы направленные. Очень благодарен буду.

хм.. честно говоря, не знаю что есть изоморфизм относительно графов (или чего там), но вот относительно групп\колец\полей - это пожалуйста
функция F есть изоморфизм, если она:
1) биекция, действует из одной группы\поля\кольца в другое
2) сопряжена с бинарными операциями в группе\кольце\поле -
пример - F(a*b) = F(a)*F(b)
(* - это не умножение, это б.о.)

вот =)

Цитата DEiL, 20.11.02, 23:53:38

1) биекция, действует из одной группы\поля\кольца в другое
2) сопряжена с бинарными операциями в группе\кольце\поле -
пример - F(a*b) = F(a)*F(b)
(* - это не умножение, это б.о.)
вот =)

Ого. Хоть кто-то знает. Так у нас надо графы проверять \%( Гадость. А можно на примере? Кстати - Биекция не может действовать из одной группы в другую, а наоборот - нет \%) Это, по определению биекции. А вот со вторым я немного запутался. Это как?

Слова "одинаковые" и "изоморфные", кстати, синонимы, только одно русское, а другое вражеское. Так вопрос-то, собственно, в чем? Понять какие графы считаются изоморфными друг другу, или как написать программу, которая проверит одинаковы два графа или нет?

Цитата S.Yu.Gubanov, 21.11.02, 10:25:37

Слова "одинаковые" и "изоморфные", кстати, синонимы, только одно русское, а другое вражеское. Так вопрос-то, собственно, в чем? Понять какие графы считаются изоморфными друг другу, или как написать программу, которая проверит одинаковы два графа или нет?

Нда. Для моего препода смысл один - доказать ему, что я понял это. А как я понял - это уже он будет смотреть. Да, надо написать программку на паскале. Ну и понять, что же такое 2 изоморфоных графа. То есть ЧТО это - я знаю. Алгоритм нужен сам для программки. Просто списывать не хочу у других. Полгруппы уже защитили одну и ту же прогу, поменяв цвета и манеру вывода. А толк списывать - если сам не разобрался? Вот... может кто поможет \%)

Для начала, предположим, что графы маленькие - а то с этим алгоритмом программа до конца века не закончит.
Во-вторых, позволю себе воспользоваться С++ - Паскаль я начал подзабывать (read-only )

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

<br>class CNode //вершина графа<br>{<br>    int IncomingCount; //количество входящих рёбер<br>    int OutgoingCount; //количество исходящих рёбер<br>    CNode** IncomingNodes;//массив ссылок на "входящие вершины"<br>    CNode** OutgoingNodes;//массив ссылок на "исходящие вершины"<br>}<br><br>class CGraph //собственно граф<br>{<br>    int Count;//количество вершин графа<br>    CNode** Items;//собственно вершины<br>}<br>

Очевидно, что графы с разным количеством вершин не могут быть изоморфны.

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

Вопросы есть?

Сообщение отредактировано: volatile - 21.11.02, 21:38

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

Мда, не повезло тебе немного . Дело в том, что была у меня в свое время курсовая, по графам, где в частности была проверка на изоморфность. Как раз на паскале. Но вот только во время летнего апгрейда, потерялась она вместе со всеми другими моими старенькими програмками.  А жаль... :-/

Цитата Faust, 22.11.02, 00:32:03

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

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

Пусть имеем четырёхугольник ABCD с диагональю AC (точнее A->B->C->D->A, A->C)
Тогда, в этой последовательности (ABCD) матрица выглядит так: (буквы написаны для удобства)
  A B C D
A 0 1 1 0
B 0 0 1 0
C 0 0 0 1
D 1 0 0 0

в последовательности ACBD имеем

  A C B D
A 0 1 1 0
C 0 0 0 1
B 0 1 0 0
D 1 0 0 0

т.е. переставляются ОДНОВРЕМЕННО соответствующие строки и столбцы.
Так понятно?

Примечание: в моём варианте, наличие ребра X->Y соответствует 1 в строке X и столбце Y

Сообщение отредактировано: volatile - 22.11.02, 21:40

Цитата Faust, 23.11.02, 00:37:55

Так понятно?

Плохо, но в суть я въехал уже. А не можешь как-нибудь попроще? Ну типа взять два графа и показать? Я даже не понял в какой последовательности и какие строки и столбцы ты переставил \%( Ну вот такой я. Странно только почему - на лекции вроде все в инст хожу. =)

Ну вот, смотри:
Тот граф, о котором я говорил выше - это четыре вершины: A,B,C,D и пять стрелок: A->B, B->C, C->D, D->A, A->C

А преставлял я вершины - B<->C

Переставлял не в самом графе, а в его представлении. При этом, матрица инцидентности меняется - меняются местами строки B и C и, одновременно столбцы B и C.

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

Посколько сравнивать придётся матрицы n*n, а всего перестановок n!, то разумно будет сократить количество тех перестановок, которые имеют смысл. Как это сделать?

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

A (1,2)
B (1,1)
C (2,1)
D (1,1)

Получаем три группы вершин: {A}, {B,D}, {C}

Так вот, вместо 24 (4!) перестановок, достаточно просто отсортировать вершины в обоих графах по соответствующим парам (например, сначала по Inc, потом по Out), и разумных перестановок будет только 2=1!*2!*1! (т.е. произведение факториалов мощностей групп вершин).

Впрочем, это к вопросу об оптимизации (а то уж очень медленный алгоритм получался!)

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

Вопросы?

Цитата S.Yu.Gubanov @ 21.11.02, 07:25

Слова "одинаковые" и "изоморфные", кстати, синонимы, только одно русское, а другое вражеское. Так вопрос-то, собственно, в чем? Понять какие графы считаются изоморфными друг другу, или как написать программу, которая проверит одинаковы два графа или нет?

Не правда, у изоморфных вершины могут быть пронумерованны по другому.