(Чтобы быть удаленным), Находят изоморфизм между двумя графиками
graphisomorphism будет удален в будущем релизе. Использование isomorphism вместо этого.
[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 boolean. Когда 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, подразумевать, что направлены оба графика.
[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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).
