transclosure

推移閉包

構文

H = transclosure(G)

説明

H = transclosure(G) は、グラフ G の推移閉包を新規グラフ H として返します。H のノードは G と同じですが、H には追加のエッジがあります。G にノード i からノード j への経路がある場合、H にはノード i とノード j を結ぶエッジがあります。同じ 2 つのノード間に複数のエッジがある多重グラフでは、出力グラフでこれらが単一エッジに置き換えられます。

例

グラフの推移閉包

有向グラフを作成してプロットします。

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 について到達可能性の質問に答えることができます。

G のノード 1 から到達可能なノードを求めます。これらのノードは、推移閉包グラフ 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 の推移閉包の隣接行列を計算します。結果は "到達可能性行列" となります。この行列には、各ノードから到達可能なノードを示す非ゼロ値が含まれます。

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 行目を見ればわかります。この行は、ノード 5 と 6 のみノード 3 から到達可能であることを示しています。

find(R(3,:))

ans = 1×2

     5     6

入力引数

G — 入力グラフ

digraph オブジェクト

入力グラフ。digraph オブジェクトとして指定します。digraph を使用して、有向グラフ オブジェクトを作成します。

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

出力引数

H — G の推移閉包

digraph オブジェクト

G の推移閉包。digraph オブジェクトとして返されます。テーブル G.Nodes は H にコピーされますが、G.Edges のプロパティはすべて破棄されます。

ノード n から到達可能な G 内のノードを調べるには、successors(H,n) を使用します。

詳細

推移閉包

グラフの推移閉包はノード間の経路を表現します。グラフにノード i からノード j への経路がある場合、そのグラフの推移閉包にノード i とノード j を結ぶエッジがあります。したがって、グラフの特定ノードについて、推移閉包は任意の到達可能なノードをそのノードの後続 (下位) ノードにします。

バージョン履歴

R2015b で導入

参考

digraph | transreduction | conncomp | successors | predecessors