изоморфизм

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

Синтаксис

P = isomorphism(G1,G2)
P = isomorphism(___,Name,Value)
[P,edgeperm] = 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)

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

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

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

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

Вычислите изоморфизм между графиками, игнорируя свойство 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 array
    {'d'}    {'c'}
    {'e'}    {'a'}
    {'f'}    {'b'}

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

свернуть все

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

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

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

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

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

Укажите необязательные аргументы в виде пар ""имя, значение"", разделенных запятыми. Имя (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

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