isisomorphic

Определите, изоморфны ли два графика

Синтаксис

tf = isisomorphic(G1,G2)
tf = isisomorphic(G1,G2,Name,Value)

Описание

пример

tf = isisomorphic(G1,G2) возвращает логический 1 (true), если изоморфизм графов существует между графиками G1 и G2; в противном случае возвращается логический 0 (false).

пример

tf = isisomorphic(G1,G2,Name,Value) задает дополнительные опции с одним или несколькими аргументами пары "имя-значение". Например, можно задать 'NodeVariables' и список переменных узла, чтобы указать, что изоморфизм должен сохранить эти переменные, чтобы быть допустимым.

Примеры

свернуть все

Создайте и постройте двух ориентированных графов, и затем определите, изоморфны ли они.

G1 = digraph([1 1 1 2 3 4],[2 3 4 4 4 1]);
G2 = digraph([3 3 3 2 1 4],[1 4 2 3 2 2]);
subplot(1,2,1)
plot(G1)
subplot(1,2,2)
plot(G2)

isisomorphic(G1,G2)
ans = logical
   1

Создайте и постройте два графика, G1 и G2.

G1 = graph([1 1 1 2 2 3 3 4 5 5 7 7],[2 4 5 3 6 4 7 8 6 8 6 8]);
plot(G1,'XData',[1 4 4 1 2 3 3 2],'YData',[4 4 1 1 3 3 2 2])

G2 = graph({'a' 'a' 'a' 'b' 'b' 'b' 'c' 'c' 'c' 'd' 'd' 'd'}, ...
    {'g' 'h' 'i' 'g' 'h' 'j' 'g' 'i' 'j' 'h' 'i' 'j'});
plot(G2,'XData',[1 2 2 2 1 2 1 1],'YData',[4 4 3 2 3 1 2 1])

Определите, существует ли изоморфизм для G1 и G2. Результат показывает, что графики являются структурно тем же самым несмотря на свои различные метки и размещения.

tf = isisomorphic(G1,G2)
tf = logical
   1

Используйте два различных сравнения, чтобы определить, существует ли отношение изоморфизма между двумя графиками. Одно из сравнений сохраняет свойство узла, в то время как другой игнорирует его.

Создайте два подобных графика. Добавьте свойство Color узла в каждый из графиков.

G1 = graph({'d' 'e' 'f'},{'e' 'f' 'd'});
G1.Nodes.Color = {'red' 'red' 'blue'}';

G2 = graph({'a' 'b' 'c'},{'b' 'c' 'a'});
G2.Nodes.Color = {'blue' 'blue' 'red'}';

Постройте графики бок о бок в той же фигуре. Окрасьте узлы в красный, которые имеют Color = 'red'.

subplot(1,2,1)
p1 = plot(G1);
highlight(p1,{'d' 'e'},'NodeColor','r')

subplot(1,2,2)
p2 = plot(G2);
highlight(p2,'c','NodeColor','r')

Определите, изоморфны ли графики, игнорируя свойство Color.

tf = isisomorphic(G1,G2)
tf = logical
   1

Определите, изоморфны ли графики и сохраняют значение свойства Color в сравнении. В этом случае нет никакого изоморфизма, поскольку свойство Color каждого графика содержит различные количества значений 'blue' и 'red'.

tf = isisomorphic(G1,G2,'NodeVariables','Color')
tf = logical
   0

Входные параметры

свернуть все

Введите графики, заданные в качестве отдельных аргументов объектов digraph или graph. Используйте граф для создания неориентированного графа или диграф для создания ориентированного графа.

G1 и G2 должны быть оба объектами graph или обоими объектами digraph.

Пример: G1 = graph(1,2)

Пример: G1 = digraph([1 2],[2 3])

Аргументы в виде пар имя-значение

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (Name) — это имя аргумента, а значение (Value) — соответствующее значение. Name должен появиться в кавычках. Вы можете задать несколько аргументов в виде пар имен и значений в любом порядке, например: Name1, Value1, ..., NameN, ValueN.

Пример: tf = isisomorphic(G1,G2,'NodeVariables',{'Var1' 'Var2'})

Переменные ребра, чтобы сохранить, заданный как пара, разделенная запятой, состоящая из 'EdgeVariables' и вектора символов, представляют в виде строки скаляр, массив ячеек из символьных векторов или массив строк. Используйте эту опцию, чтобы задать одну или несколько переменных ребра, которые находятся и в G1.Edges и в G2.Edges. Сравнение изоморфизма должно сохранить заданные переменные ребра в порядке быть допустимым. Для мультиграфов с несколькими ребрами между теми же двумя узлами упорядоченное расположение переменных ребра для той же пары узла не важно.

Типы данных: char | string | cell

Переменные узла, чтобы сохранить, заданный как пара, разделенная запятой, состоящая из 'NodeVariables' и вектора символов, представляют в виде строки скаляр, массив ячеек из символьных векторов или массив строк. Используйте эту опцию, чтобы задать одну или несколько переменных узла, которые находятся и в G1.Nodes и в G2.Nodes. Сравнение изоморфизма должно сохранить заданные переменные узла в порядке быть допустимым.

Типы данных: char | string | cell

Больше о

свернуть все

Изоморфизм графов

Два графика, G1 и G2, изоморфны, если там существует перестановка узлов P, таким образом, что reordernodes(G2,P) имеет ту же структуру как G1.

Два графика, которые изоморфны, имеют подобную структуру. Например, если график содержит один цикл, то все графики, изоморфные к тому графику также, содержат один цикл.

Введенный в R2017b

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