hascycles

グラフに循環があるかどうかを判別

R2021a 以降

構文

tf = hascycles(G)

説明

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

例

無向グラフに循環があるかどうかを判別

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

G = graph([1 1 1 1],[2 3 4 5]);
plot(G)

グラフに循環があるかどうかを判別します。

tf = hascycles(G)

tf = logical
   0

ここで、グラフのノード 2 とノード 3 の間にエッジを追加します。グラフを再プロットします。

G = addedge(G,2,3);
plot(G)

新しいグラフに循環があるかどうかを判別します。

tf2 = hascycles(G)

tf2 = logical
   1

有向グラフに循環があるかどうかを判別

有向グラフに対する関数 hascycles と関数 isdag の動作の違いを調べます。

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

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

グラフに循環があるかどうかを判別します。

tf = hascycles(G)

tf = logical
   1

有向グラフに循環がある場合、hascycles は true を返します。

次に、isdag を使用して、グラフが有向で非循環であるかどうかを判別します。

tf2 = isdag(G)

tf2 = logical
   0

グラフに循環があるため、isdag は false を返します。一般に、有向グラフについては、関数 hascycles と関数 isdag は反対の結果を返します。

入力引数

G — 入力グラフ

graph オブジェクト | digraph オブジェクト

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

例: G = graph(1,2)

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

詳細

グラフの循環

グラフに循環が存在するのは、最初と最後のノードのみが繰り返される空でない経路がある場合です。循環は、たとえば (Node1 - Node2 - Node3 - Node1) のようになります。

循環が同じエッジを 2 回通過することはありません。たとえば、無向グラフに循環 (Node1 - Node2 - Node1) が存在するのは、Node1 と Node2 を連結するエッジが複数ある場合のみになります。この定義により、自己ループは循環としてカウントされますが、それよりも大きい循環の一部となることはありません。

バージョン履歴

R2021a で導入

参考

allcycles | cyclebasis | isdag