Найти изоморфизм между двумя биографическими объектами
[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] Маккей, бакалавр наук (1981). Практический изоморфизм графов. Конгрессу Нумерантия 30, 45-87.
[3] Сиек, Дж. Г., Ли, L-Q, и Люмсдейн, А. (2002). Руководство пользователя и справочное руководство библиотеки Boost Graph (Upper Saddle River, NJ: Pearson Education).
allshortestpaths | biograph | conncomp | graphisomorphism | isdag | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse