isomorphism

두 그래프 간의 동형사상 계산

구문

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'}';

동일한 Figure에 그래프를 나란히 플로팅합니다. 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
    {'d'}    {'c'}
    {'e'}    {'a'}
    {'f'}    {'b'}

입력 인수

G1,G2 — 입력 그래프(개별 인수)

graph 객체 | digraph 객체

입력 그래프로, graph 객체나 digraph 객체로 구성된 개별 인수로 지정됩니다. 무방향 그래프를 생성하려면 graph를 사용하고 유방향 그래프를 생성하려면 digraph를 사용하십시오.

G1과 G2는 모두 graph 객체이거나 모두 digraph 객체여야 합니다.

예: G1 = graph(1,2)

예: G1 = digraph([1 2],[2 3])

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: P = isomorphism(G1,G2,'NodeVariables',{'Var1' 'Var2'})

EdgeVariables — 유지할 간선 변수

문자형 벡터 | string형 스칼라 | 문자형 벡터로 구성된 셀형 배열 | string형 배열

유지할 간선 변수로, 'EdgeVariables'와 함께 문자형 벡터, string형 스칼라, 문자형 벡터로 구성된 셀형 배열 또는 string형 배열이 쉼표로 구분되어 지정됩니다. G1.Edges와 G2.Edges 모두에 있는 간선 변수를 하나 이상 지정하려면 이 옵션을 사용하십시오. 동형사상이 유효하려면 지정된 간선 변수를 유지해야 합니다.

G가 다중 그래프인 경우, 두 번째 출력값 edgeperms를 지정하여 간선 변수를 재정렬할 수 있습니다.

데이터형: char | string | cell

NodeVariables — 유지할 노드 변수

문자형 벡터 | string형 스칼라 | 문자형 벡터로 구성된 셀형 배열 | string형 배열

유지할 노드 변수로, 'NodeVariables'와 함께 문자형 벡터, string형 스칼라, 문자형 벡터로 구성된 셀형 배열 또는 string형 배열이 쉼표로 구분되어 지정됩니다. G1.Nodes와 G2.Nodes 모두에 있는 노드 변수를 하나 이상 지정하려면 이 옵션을 사용하십시오. 동형사상이 유효하려면 지정된 노드 변수를 유지해야 합니다.

데이터형: char | string | cell

출력 인수

P — 동형사상의 치환 벡터

열 벡터 | []

동형사상의 치환 벡터로, 동형사상이 존재할 경우 열 벡터로 반환되고 동형사상이 존재하지 않을 경우 빈 배열 []로 반환됩니다. P가 비어 있지 않으면 reordernodes(G2,P)가 G1과 동일한 구조를 갖습니다.

edgeperm — 간선 치환

열 벡터

간선 치환으로, 열 벡터로 반환됩니다. 다중 그래프로 작업을 하는 경우, 간선 치환 벡터를 사용하여 '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과 동일한 구조를 갖는 경우 동형입니다.

동형인 두 그래프는 유사한 구조를 갖습니다. 예를 들어, 하나의 순환이 포함된 그래프와 동형인 모든 그래프는 하나의 순환을 포함합니다.

버전 내역

R2016b에 개발됨

참고 항목

graph | digraph | isisomorphic | reordernodes

도움말 항목

• 유방향 그래프와 무방향 그래프

×

예제 열기

이 예제의 수정된 버전이 있습니다. 사용자가 편집한 내용을 반영하여 이 예제를 여시겠습니까?

아니요, 수정된 버전을 덮어씁니다. 예