transclosure

전이적 폐포(Transitive Closure)

구문

H = transclosure(G)

설명

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

예제

그래프의 전이적 폐포(Transitive Closure)

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

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)

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

H = transclosure(G);
plot(H)

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

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

입력 인수

G — 입력 그래프

digraph 객체

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

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

출력 인수

H — G의 전이적 폐포(Transitive Closure)

digraph 객체

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

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

세부 정보

전이적 폐포(Transitive Closure)

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

버전 내역

R2015b에 개발됨

참고 항목

digraph | transreduction | conncomp | successors | predecessors