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) возвращает логический 1 (true) в Isomorphic если G1 и G2 изоморфные графы и логический 0 (false) в противном случае. Изоморфизм графа - это отображение узлов графа 1 в 1. G1 и узлы на графике G2 так, что смежности сохраняются. G1 и G2 оба являются N-на-N разреженными матрицами, которые представляют направленные или неориентированные графы. Возвращаемое значение Isomorphic является логическим. Когда Isomorphic является true, Map - вектор строки, содержащий индексы узлов, которые сопоставляются с G2 кому G1 для одного возможного изоморфизма. Когда Isomorphic является false, Map пуст. Наихудшая сложность времени - 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] Фортин, С. (1996). Проблема изоморфизма графа. Технический отчет, 96-20, департамент компьютерных наук, Университет Альберты, Эдомонтон, Альберта, Канада.

[2] Маккей, бакалавр наук (1981). Практический изоморфизм графов. Конгрессу Нумерантия 30, 45-87.

[3] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).

См. также

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

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