transreduction

推移還元

構文

H = transreduction(G)

説明

H = transreduction(G) は、グラフ G の推移還元を新規グラフ H として返します。H のノードは G と同じですが、H のエッジは異なっています。H には、G にノード i からノード j への経路が 1 本ある場合に、H にもノード i からノード j への経路が 1 本あるようにする最小数のエッジが含まれています。

例

完全グラフの推移還元

次数 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)

推移還元を求め、結果として得られたグラフをプロットします。完全グラフの到達可能性は網羅的なので、理論的に複数の推移還元が可能です。これは、4 つのノードを通過する循環がすべて候補になるからです。

H = transreduction(G);
plot(H)

同じ到達可能性をもつ 2 つのグラフでは、推移還元も同じです。そのため、4 ノードの任意の循環は H と同じ推移還元を生成します。

次の異なる 4 ノードの循環を含む有向グラフを作成します: (1,3,4,2,1)

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

G1 の推移還元を求めます。推移還元 H および H1 が同じ循環 (1,2,3,4,1) をもつように、G1 の循環が並べ替えられます。

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 を使用して、有向グラフ オブジェクトを作成します。

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

出力引数

H — G の推移還元

digraph オブジェクト

G の推移還元。digraph オブジェクトとして返されます。テーブル G.Nodes は H にコピーされますが、G.Edges のプロパティはすべて破棄されます。H には、G に存在しない新規のエッジが含まれることがあります。

H は、グラフ G の到達可能性を保持する最小数のエッジを含みます。つまり、transclosure(H) は transclosure(G) と同じです。

isdag(G) が true の場合 H は一意であり、G の部分グラフとなります。

詳細

推移還元

グラフ G の推移還元は、G と同じ到達可能性をもつ、エッジ数が最小のグラフです。したがって、G と同じ推移閉包をもつすべてのグラフの中で、推移還元はエッジ数が最小となります。2 つの有向グラフの推移閉包が同じである場合、それらの推移還元も同じになります。

バージョン履歴

R2015b で導入

参考

digraph | transclosure | conncomp