transreduction
推移還元
説明
例
完全グラフの推移還元
次数 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)
入力引数
出力引数
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 で導入
参考
MATLAB コマンド
次の MATLAB コマンドに対応するリンクがクリックされました。
コマンドを MATLAB コマンド ウィンドウに入力して実行してください。Web ブラウザーは MATLAB コマンドをサポートしていません。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)