Найдите изоморфизм между двумя графиками
[
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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).
graphallshortestpaths
| graphconncomp
| graphisdag
| graphisspantree
| graphmaxflow
| graphminspantree
| graphpred2path
| graphshortestpath
| graphtopoorder
| graphtraverse
| isomorphism