isomorphism

Вычислите изоморфизм между двумя графиками

Описание

пример

P = isomorphism(G1,G2) вычисляет отношение эквивалентности изоморфизма графов между графиками G1 и G2, если вы существуете. Если никакой изоморфизм не существует, то P пустой массив.

пример

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

[P,edgeperm] = isomorphism(___) дополнительно возвращает вектор из сочетаний ребра, edgeperm. Этот выход позволяет вам сохранить переменные ребра при работе с мультиграфами.

Примеры

свернуть все

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

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)

Figure contains 2 axes. Axes 1 contains an object of type graphplot. Axes 2 contains an object of type graphplot.

p = isomorphism(G1,G2)
p = 4×1

     3
     1
     4
     2

Результат показывает на тот reordernodes(G2,p) имеет ту же структуру как G1.

Создайте и постройте два графика, 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])

Figure contains an axes. The axes contains an object of type graphplot.

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])

Figure contains an axes. The axes contains an object of type graphplot.

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

p = isomorphism(G1,G2)
p = 8×1

     1
     2
     5
     3
     4
     7
     6
     8

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

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

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

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

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

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

subplot(1,2,2)
p2 = plot(G2);
highlight(p2,{'a' 'b'},'NodeColor','r')

Figure contains 2 axes. Axes 1 contains an object of type graphplot. Axes 2 contains an object of type graphplot.

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

p = isomorphism(G1,G2)
p = 3×1

     1
     2
     3

Вычислите изоморфизм снова, но на этот раз сохраните значение Color свойство в сравнении. isomorphism возвращает различную перестановку, которая сохраняет Color свойство.

p = isomorphism(G1,G2,'NodeVariables','Color')
p = 3×1

     3
     1
     2

Просмотрите узлы в G1 и G2 то, что изоморфизм соответствует вместе.

[G1.Nodes.Name, G2.Nodes.Name(p)]
ans = 3x2 cell
    {'d'}    {'c'}
    {'e'}    {'a'}
    {'f'}    {'b'}

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

свернуть все

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

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

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

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

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

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

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

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

Если G мультиграф, затем можно задать второй выход edgeperms позволять переупорядочить переменные ребра.

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

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

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

Выходные аргументы

свернуть все

Вектор сочетания для изоморфизма, возвращенного как вектор-столбец, когда изоморфизм существует или как пустой массив [] когда изоморфизм не существует. Если P не пусто, затем reordernodes(G2,P) имеет ту же структуру как G1.

Сочетание ребра, возвращенное как вектор-столбец. При работе с мультиграфами вектор сочетания ребра позволяет вам сохранить переменные ребра, заданные 'EdgeVariables' пара "имя-значение". Используйте эти команды, чтобы переупорядочить переменные ребра повторных ребер:

[p,edgeperm] = isomorphism(g1,g2,'EdgeVariables',edgevars);
g2perm = reordernodes(g2, p);
g2perm.Edges(:, 2:end) = g2perm.Edges(edgeperm, 2:end);

Больше о

свернуть все

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

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

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

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