Найдите изоморфизм между двумя объектами биографика
[
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