Main Content

transclosure

전이적 폐포(Transitive Closure)

설명

H = transclosure(G)는 그래프 G전이적 폐포를 새 그래프 H로 반환합니다. H의 노드는 G와 동일하지만, H에는 추가 간선이 포함됩니다. G에는 노드 i부터 노드 j까지의 경로가 포함되고 H에는 노드 i와 노드 j 사이의 간선이 포함됩니다. 동일한 두 노드 사이에 다중 간선이 있는 다중 그래프에서는 출력 그래프가 이를 단일 간선으로 바꿉니다.

예제

예제

모두 축소

유방향 그래프를 생성하고 플로팅합니다.

G = digraph([1 2 3 4 4 4 5 5 5 6 7 8],[2 3 5 1 3 6 6 7 8 9 9 9]);
plot(G)

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

그래프 G의 전이적 폐포를 찾고, 결과로 생성되는 그래프를 플로팅합니다. H에는 G와 동일한 노드가 포함되고, 추가 간선이 포함됩니다.

H = transclosure(G);
plot(H)

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

H에 들어 있는 전이적 폐포 정보는 원본 그래프 G의 도달 가능성 질문에 대한 답으로 볼 수 있습니다.

노드 1에서 도달할 수 있는 G의 노드를 확인합니다. 이러한 노드는 전이적 폐포 그래프 H의 노드 1의 후속 노드입니다.

N = successors(H,1)
N = 7×1

     2
     3
     5
     6
     7
     8
     9

유방향 그래프를 생성하고 플로팅합니다.

s = [1 1 2 2 3 4 4 5];
t = [2 4 3 4 5 5 6 6];
G = digraph(s,t);
plot(G,'Layout','subspace')

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

G의 전이적 폐포의 인접 행렬을 계산합니다. 결과는 도달 가능성 행렬로, 이 행렬은 각 노드에서 도달 가능한 노드를 나타내는 0이 아닌 값을 갖습니다.

D = transclosure(G);
R = full(adjacency(D))
R = 6×6

     0     1     1     1     1     1
     0     0     1     1     1     1
     0     0     0     0     1     1
     0     0     0     0     1     1
     0     0     0     0     0     1
     0     0     0     0     0     0

예를 들어, "노드 3에서 도달 가능한 노드는 무엇인가?"라는 질문에 답하려면 이 행렬의 3번째 행을 확인하면 됩니다. 이 행을 확인하여 노드 3에서는 노드 5와 6에만 도달할 수 있음을 알 수 있습니다.

find(R(3,:))
ans = 1×2

     5     6

입력 인수

모두 축소

입력 그래프로, digraph 객체로 지정됩니다. digraph를 사용하여 유방향 graph 객체를 생성할 수 있습니다.

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

출력 인수

모두 축소

G의 전이적 폐포로, digraph 객체로 반환됩니다. 테이블 G.NodesH로 복사되지만, G.Edges의 속성은 삭제됩니다.

successors(H,n)을 사용하여 노드 n에서 도달할 수 있는 G의 노드를 확인할 수 있습니다.

세부 정보

모두 축소

전이적 폐포(Transitive Closure)

그래프의 전이적 폐포는 노드 사이의 경로를 설명합니다. 원래 그래프에 노드 i로부터 노드 j로의 경로가 존재한다면 두 노드 i, j 간의 간선이 전이적 폐포 그래프에 그려지게 됩니다. 전이적 폐포에서는, 원래 그래프의 한 노드에서 도달 가능한 모든 노드가 이 노드의 직접적인 후속 노드(후손)로 그려집니다.

버전 내역

R2015b에 개발됨