isdag

グラフが非循環かどうかの判定

構文

tf = isdag(G)

tf = isdag(G) は、G が有向非循環グラフである場合に logical 1 (true) を返します。それ以外の場合は、logical 0 (false) を返します。

有向グラフを作成してプロットし、次にグラフをテストして非循環かどうかを判定します。

s = [1 1 2 2 3 3 4 4 4 5];
t = [2 3 4 5 6 7 8 9 10 4];
G = digraph(s,t)

G = 
  digraph with properties:

    Edges: [10×1 table]
    Nodes: [10×0 table]

plot(G)

Figure contains an axes object. The axes object contains an object of type graphplot.

tf = isdag(G)

tf = logical
   1

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

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

循環を含まない有向グラフは非循環です。つまり、グラフの任意のノードから開始し、どの一連のエッジに沿って進んでもその開始ノードにループバックできません。その結果、有向非循環グラフには自己ループがありません。

R2015b で導入