Найдите изоморфизм между двумя объектами биографика
[Isomorphic, Map]
= isomorphism(BGObj1, BGObj2)
[Isomorphic, Map]
= isomorphism(BGObj1, BGObj2,'Directed', DirectedValue)
BGObj1 | Объект биографика, созданный biograph (конструктор объектов). |
BGObj2 | Объект биографика, созданный biograph (конструктор объектов). |
DirectedValue | Свойство, которое указывает, направлены ли графики или не направлены. Введите false когда оба BGObj1 и BGObj2 создать неориентированные графы. В этом случае верхние треугольники разреженных матриц, извлеченные из BGObj1 и BGObj2 игнорируются. По умолчанию это true, что означает, что оба графиков направлены. |
Совет
Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».
[ возвращает логический 1 (Isomorphic, Map]
= isomorphism(BGObj1, BGObj2)true) в Isomorphic если две N-на-N матрицы смежности, извлеченные из объектов биографика BGObj1 и BGObj2 являются изоморфными графиками и логическими 0 (false) в противном случае. Изоморфизм графика является отображением 1 на 1 узлов в графике из BGObj1 и узлы в графике из BGObj2 таким образом, что смежности сохраняются. Возвращаемое значение Isomorphic является логическим. Когда Isomorphic является true, Map - вектор-строка, содержащая индексы узлов, которые сопоставлены с BGObj2 на BGObj1. Когда Isomorphic является falseнаихудшая временная сложность O(N!), где N является число узлов.
[ указывает, направлены ли графики или не направлены. Задайте Isomorphic, Map]
= isomorphism(BGObj1, BGObj2,'Directed', DirectedValue)DirectedValue на false когда оба BGObj1 и BGObj2 создать неориентированные графы. В этом случае верхние треугольники разреженных матриц, извлеченные из BGObj1 и BGObj2 игнорируются. Значение по умолчанию является true, что означает, что оба графиков направлены.
[1] Фортин, С. (1996). Задача изоморфизма графика. Технический отчет, 96-20, департамент компьютерных наук, Университет Альберты, Эдомонтон, Альберта, Канада.
[2] McKay, B.D. (1981). Практический изоморфизм графика. Конгресс-нумерация 30, 45-87.
[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). Руководство пользователя библиотеки График (Upper Saddle River, NJ: Pearson Education).
allshortestpaths | biograph | conncomp | graphisomorphism | isdag | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse