transreduction

전이적 축약(Transitive Reduction)

구문

H = transreduction(G)

설명

H = transreduction(G)는 그래프 G의 전이적 축약을 새 그래프, H로 반환합니다. H의 노드는 G와 동일하지만, H의 간선은 G와 다릅니다. H에는 최소의 간선이 포함됩니다. G에 노드 i로부터 노드 j로의 경로가 있다면 H에도 노드 i로부터 노드 j로의 경로가 존재하게 됩니다.

예제

완전 그래프(Complete Graph)의 전이적 축약

차수가 4인 완전 그래프를 생성하고 플로팅합니다.

G = digraph([1 1 1 2 2 2 3 3 3 4 4 4],[2 3 4 1 3 4 1 2 4 1 2 3]);
plot(G)

전이적 축약을 찾고, 결과로 생성된 그래프를 플로팅합니다. 네 노드를 통한 순환이 모두 가능하므로 완전 그래프의 도달 가능성 범위는 한정 짓기 어렵습니다. 이러한 경우 이론상으로 가능한 전이적 축약은 여러 가지가 있을 수 있습니다.

H = transreduction(G);
plot(H)

도달 가능성이 동일한 두 그래프는 전이적 축약도 동일합니다. 따라서 네 노드의 순환은 H와 동일한 전이적 축약 결과를 생성합니다.

다음 서로 다른 네 가지 순환이 포함된 유방향 그래프를 생성합니다. (1,3,4,2,1).

G1 = digraph([1 3 4 2],[3 4 2 1]);
plot(G1)

G1의 전이적 축약을 찾습니다. G1의 순환이 재정렬되므로 전이적 축약 H와 H1은 순환(1,2,3,4,1)이 동일합니다.

H1 = transreduction(G1);
plot(H1)

고유한 전이적 축약

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

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

G에 순환이 포함되어 있지 않은지 확인합니다.

tf = isdag(G)

tf = logical
   1

그래프의 전이적 축약을 찾습니다. 그래프에 순환이 포함되어 있지 않으므로 전이적 축약은 고유하며 G의 부분 그래프가 됩니다.

H = transreduction(G);
plot(H)

입력 인수

G — 입력 그래프

digraph 객체

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

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

출력 인수

H — G의 전이적 축약

digraph 객체

G의 전이적 축약(Transitive Reduction)으로, digraph 객체로 반환됩니다. 테이블 G.Nodes가 H로 복사되지만, G.Edges의 속성은 삭제됩니다. H에는 G에 있지 않은 새 간선이 포함될 수 있습니다.

H는 그래프 G의 도달 가능성은 유지하면서 간선은 최소로 갖는 그래프입니다. 즉, transclosure(H)는 transclosure(G)와 동일합니다.

isdag(G)가 true이면 H는 고유하며 G의 부분 그래프가 됩니다.

세부 정보

전이적 축약

그래프 G의 전이적 축약은 G와 도달 가능성은 동일하면서 간선 개수는 최소로 갖는 그래프입니다. 따라서 전이적 축약은 G와 전이적 폐포(Transitive Closure)가 동일한 모든 그래프 중에서 간선 개수가 가장 적은 그래프입니다. 전이적 폐포가 동일한 두 유방향 그래프는 전이적 축약도 동일합니다.

버전 내역

R2015b에 개발됨

참고 항목

digraph | transclosure | conncomp