isomorphism (biograph)

Найдите изоморфизм между двумя объектами биографика

Синтаксис

[Isomorphic, Map] = isomorphism(BGObj1, BGObj2)
[Isomorphic, Map] = isomorphism(BGObj1, BGObj2,'Directed', DirectedValue)

Аргументы

BGObj1 Объект биографика, созданный biograph (конструктор объектов).
BGObj2 Объект биографика, созданный biograph (конструктор объектов).
DirectedValueСвойство, которое указывает, направлены ли графики или не направлены. Введите false когда оба BGObj1 и BGObj2 создать неориентированные графы. В этом случае верхние треугольники разреженных матриц, извлеченные из BGObj1 и BGObj2 игнорируются. По умолчанию это true, что означает, что оба графиков направлены.

Описание

Совет

Для получения вводной информации о функциях теории графиков, см. «Функции теории графиков».

[Isomorphic, Map] = isomorphism(BGObj1, BGObj2) возвращает логический 1 (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).

Введенный в R2006b
Для просмотра документации необходимо авторизоваться на сайте