MATLAB ヘルプ センター
推移還元
H = transreduction(G)
H = transreduction(G) は、グラフ G の推移還元を新規グラフ H として返します。H のノードは G と同じですが、H のエッジは異なっています。H には、G にノード i からノード j への経路が 1 本ある場合に、H にもノード i からノード j への経路が 1 本あるようにする最小数のエッジが含まれています。
H
G
i
j
例
すべて折りたたむ
次数 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 の循環が並べ替えられます。
G1
H1
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 の部分グラフになります。
digraph
入力グラフ。digraph オブジェクトとして指定します。digraph を使用して、有向グラフ オブジェクトを作成します。
例: G = digraph([1 2],[2 3])
G = digraph([1 2],[2 3])
G の推移還元。digraph オブジェクトとして返されます。テーブル G.Nodes は H にコピーされますが、G.Edges のプロパティはすべて破棄されます。H には、G に存在しない新規のエッジが含まれることがあります。
G.Nodes
G.Edges
H は、グラフ G の到達可能性を保持する最小数のエッジを含みます。つまり、transclosure(H) は transclosure(G) と同じです。
transclosure(H)
transclosure(G)
isdag(G) が true の場合 H は一意であり、G の部分グラフとなります。
isdag(G)
true
グラフ G の推移還元は、G と同じ到達可能性をもつ、エッジ数が最小のグラフです。したがって、G と同じ推移閉包をもつすべてのグラフの中で、推移還元はエッジ数が最小となります。2 つの有向グラフの推移閉包が同じである場合、それらの推移還元も同じになります。
R2015b で導入
digraph | transclosure | conncomp
transclosure
conncomp
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Web サイトの選択
Web サイトを選択すると、翻訳されたコンテンツにアクセスし、地域のイベントやサービスを確認できます。現在の位置情報に基づき、次のサイトの選択を推奨します:
また、以下のリストから Web サイトを選択することもできます。
最適なサイトパフォーマンスの取得方法
中国のサイト (中国語または英語) を選択することで、最適なサイトパフォーマンスが得られます。その他の国の MathWorks のサイトは、お客様の地域からのアクセスが最適化されていません。
南北アメリカ
ヨーロッパ
アジア太平洋地域
最寄りの営業オフィスへのお問い合わせ