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

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

Синтаксис

[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 пуст. Временной сложностью худшего случая является 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