Найдите изоморфизм между двумя биообъектами диаграмм
[Isomorphic, Map]
= isomorphism(BGObj1, BGObj2)
[Isomorphic, Map]
= isomorphism(BGObj1, BGObj2,'Directed', DirectedValue)
BGObj1 | Биообъект диаграмм создается biograph (конструктор Object). |
BGObj2 | Биообъект диаграмм создается biograph (конструктор Object). |
DirectedValue | Свойство, которое указывает, направлены ли графики или неориентированные. Введите false, когда и BGObj1 и BGObj2 произведут неориентированных графов. В этом случае верхние треугольники разреженных матриц, извлеченных от BGObj1 и BGObj2, проигнорированы. Значением по умолчанию является true, означая, что направлены оба графика. |
Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.
[ возвращает логическую единицу (Isomorphic, Map]
= isomorphism(BGObj1, BGObj2)true) в Isomorphic, если две N на n матрицы смежности, извлеченные от биообъектов диаграмм BGObj1 и BGObj2, являются изоморфными графиками и логическим нолем (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] Fortin, S. (1996). Проблема изоморфизма графов. Технический отчет, 96-20, отдел информатики, Альбертский университет, Edomonton, Альберта, Канада.
[2] Маккей, B.D. (1981). Практический изоморфизм графов. Congressus Numerantium 30, 45-87.
[3] Siek, J.G., Ли, L-Q и Lumsdaine, A. (2002). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).
allshortestpaths | biograph | conncomp | graphisomorphism | isdag | isspantree | maxflow | minspantree | shortestpath | topoorder | traverse