graphisomorphism

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

Синтаксис

[Isomorphic, Map] = graphisomorphism(G1, G2)
[Isomorphic, Map] = graphisomorphism(G1, G2,'Directed', DirectedValue)

Аргументы

G1 N на n разреженная матрица, которая представляет направленного или неориентированного графа. Ненулевые записи в матричном G1 укажите на присутствие ребра.
G2N на n разреженная матрица, которая представляет направленного или неориентированного графа. G2 должно быть то же самое (направленный или неориентированный) как G1.
DirectedValueСвойство, которое указывает, направлены ли графики или неориентированные. Введите false когда оба G1 и G2 неориентированные графы. В этом случае, верхние треугольники разреженных матриц G1 и G2 проигнорированы. Значением по умолчанию является true, подразумевать, что направлены оба графика.

Описание

Совет

Дополнительные сведения о функциях теории графов см. в Функциях Теории графов.

[Isomorphic, Map] = graphisomorphism(G1, G2) возвращает логическую единицу (true) в Isomorphic если G1 и G2 изоморфные графики и логический ноль (false) в противном случае. Изоморфизм графов является 1 к 1 отображением узлов в графике G1 и узлы в графике G2 таким образом, что соседние узлы сохраняются. G1 и G2 оба N на n разреженные матрицы, которые представляют направленных или неориентированных графов. Возвращаемое значение Isomorphic булевская переменная. Когда Isomorphic true, Map вектор-строка, содержащий индексы узла та карта от G2 к G1 для одного возможного изоморфизма. Когда Isomorphic false, Map isempty. Временной сложностью худшего случая является O(N!), где N количество узлов.

[Isomorphic, Map] = graphisomorphism(G1, G2,'Directed', DirectedValue) указывает, направлены ли графики или неориентированные. Установите DirectedValue к false когда оба G1 и G2 неориентированные графы. В этом случае, верхние треугольники разреженных матриц G1 и G2 проигнорированы. Значением по умолчанию является true, подразумевать, что направлены оба графика.

Примеры

  1. Создайте и просмотрите ориентированного графа с 8 узлами и 11 ребрами.

    m('ABCDEFGH') = [1 2 3 4 5 6 7 8];
    g1 = sparse(m('ABDCDCGEFFG'),m('BCBDGEEFHGH'),true,8,8)
    
    g1 =
    
       (1,2)        1
       (4,2)        1
       (2,3)        1
       (3,4)        1
       (3,5)        1
       (7,5)        1
       (5,6)        1
       (4,7)        1
       (6,7)        1
       (6,8)        1
       (7,8)        1
    
    view(biograph(g1,'ABCDEFGH'))

  2. Установите случайный вектор сочетания и затем создайте и просмотрите новый переставленный график.

    p = randperm(8)
     
    p =
    
         7     8     2     3     6     4     1     5
    
    g2 = g1(p,p);
    view(biograph(g2,'12345678'))
    

  3. Проверяйте, изоморфны ли эти два графика.

    [F,Map] = graphisomorphism(g2,g1)
    
    F =
    
         1
    
    
    Map =
    
         7     8     2     3     6     4     1     5
    

    Обратите внимание на то, что Map вектор-строка, содержащий индексы узла та карта от g2 к g1 совпадает с вектором сочетания, который вы создали на шаге 2.

  4. Инвертируйте направление ребра D-G в первом графике, и затем проверяйте на изоморфизм снова.

    g1(m('DG'),m('GD')) = g1(m('GD'),m('DG'));
    view(biograph(g1,'ABCDEFGH'))

    [F,M] = graphisomorphism(g2,g1)
    
    F =
    
         0
    
    
    M =
    
         []
  5. Преобразуйте графики в неориентированных графов, и затем проверяйте на изоморфизм.

    [F,M] = graphisomorphism(g2+g2',g1+g1','directed',false)
    
    F =
    
         1
    
    
    M =
    
         7     8     2     3     6     4     1     5
    

Ссылки

[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). Руководство пользователя библиотеки графика повышения и справочник, (верхний Сэддл-Ривер, образование НДЖ:ПИРСОНА).

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