graphisomorphism

Найдите изоморфизм между двумя графиками

Синтаксис

[Isomorphic, Map] = graphisomorphism(G1, G2) [Isomorphic, Map] = graphisomorphism(G1, G2,'Directed', DirectedValue)

Аргументы

`G1`	N на n разреженная матрица, которая представляет направленного или неориентированного графа. Ненулевые записи в матричном `G1` укажите на присутствие ребра.
`G2`	N на n разреженная матрица, которая представляет направленного или неориентированного графа. `G2` должно быть то же самое (направленный или неориентированный) как `G1`.
`DirectedValue`	Свойство, которое указывает, направлены ли графики или неориентированные. Введите `false` когда оба `G1` и `G2` неориентированные графы. В этом случае, верхние треугольники разреженных матриц `G1` и `G2` проигнорированы. Значением по умолчанию является `true`, подразумевать, что направлены оба графика.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[Isomorphic, Map] = graphisomorphism(G1, G2) возвращает логическую единицу (true) в Isomorphic если G1 и G2 изоморфные графики и логический ноль (false) в противном случае. Изоморфизм графов является 1 к 1 отображением узлов в графике G1 и узлы в графике G2 таким образом, что соседние узлы сохраняются. G1 и G2 оба N на n разреженные матрицы, которые представляют направленных или неориентированных графов. Возвращаемое значение Isomorphic булевская переменная. Когда Isomorphic true, Map вектор-строка, содержащий индексы узла та карта от G2 к G1 для одного возможного изоморфизма. Когда Isomorphic false, Map isempty. Временной сложностью худшего случая является O(N!), где N количество узлов.

[Isomorphic, Map] = graphisomorphism(G1, G2,'Directed', DirectedValue) указывает, направлены ли графики или неориентированные. Установите DirectedValue к false когда оба G1 и G2 неориентированные графы. В этом случае, верхние треугольники разреженных матриц G1 и G2 проигнорированы. Значением по умолчанию является true, подразумевать, что направлены оба графика.

Примеры

Создайте и просмотрите ориентированного графа с 8 узлами и 11 ребрами.

m('ABCDEFGH') = [1 2 3 4 5 6 7 8];
g1 = sparse(m('ABDCDCGEFFG'),m('BCBDGEEFHGH'),true,8,8)

g1 =

   (1,2)        1
   (4,2)        1
   (2,3)        1
   (3,4)        1
   (3,5)        1
   (7,5)        1
   (5,6)        1
   (4,7)        1
   (6,7)        1
   (6,8)        1
   (7,8)        1

view(biograph(g1,'ABCDEFGH'))

Установите случайный вектор сочетания и затем создайте и просмотрите новый переставленный график.
```
p = randperm(8)
 
p =

     7     8     2     3     6     4     1     5

g2 = g1(p,p);
view(biograph(g2,'12345678'))
```
Проверяйте, изоморфны ли эти два графика.
```
[F,Map] = graphisomorphism(g2,g1)

F =

     1


Map =

     7     8     2     3     6     4     1     5
```
Обратите внимание на то, что Map вектор-строка, содержащий индексы узла та карта от g2 к g1 совпадает с вектором сочетания, который вы создали на шаге 2.
Инвертируйте направление ребра D-G в первом графике, и затем проверяйте на изоморфизм снова.
```
g1(m('DG'),m('GD')) = g1(m('GD'),m('DG'));
view(biograph(g1,'ABCDEFGH'))
```
```
[F,M] = graphisomorphism(g2,g1)

F =

     0


M =

     []
```
Преобразуйте графики в неориентированных графов, и затем проверяйте на изоморфизм.
```
[F,M] = graphisomorphism(g2+g2',g1+g1','directed',false)

F =

     1


M =

     7     8     2     3     6     4     1     5
```

Ссылки

[1] Fortin, S. (1996). Проблема изоморфизма графов. Технический отчет, 96-20, отдел информатики, Альбертский университет, Edomonton, Альберта, Канада.

[2] Маккей, B.D. (1981). Практический изоморфизм графов. Congressus Numerantium 30, 45-87.

[3] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

Документация

graphisomorphism

Синтаксис

Аргументы

Описание

Совет

Примеры

Ссылки

Смотрите также

Представленный в R2006b

Документация Bioinformatics Toolbox

Поддержка