biconncomp

グラフの 2 重連結要素

構文

bins = biconncomp(G)

bins = biconncomp(G,'OutputForm',form)

[bins,iC] = biconncomp(___)

説明

bins = biconncomp(G) は、グラフ G の 2 重連結要素をビンとして返します。ビン番号はグラフの各エッジが属する 2 重連結要素を示します。G の各エッジは 1 つの 2 重連結要素に属していますが、G のノードは複数の 2 重連結要素に属することができます。グラフから 1 つのノードを削除してもそれらが連結したままの場合、2 つのノードが同じ 2 重連結要素に属しています。

bins = biconncomp(G,'OutputForm',form) は、form が 'cell' のときに出力を cell 配列として返します。bins{j} には要素 j のすべてのノードのノード ID が含まれます。form の既定値は 'vector' です。

[bins,iC] = biconncomp(___) はさらにどのノードが切断点 (関節点とも呼ばれる) であるかを示すノード インデックス iC も返します。

例

2 重連結要素の強調表示

グラフを作成してプロットします。各エッジの属する 2 重連結要素に基づいてエッジを色分けします。

s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
p = plot(G,'LineWidth',2);

p.EdgeCData =  biconncomp(G);

2 重連結要素を部分グラフとして抽出

この例では、グラフから 2 重連結要素を部分グラフとして抽出する方法と元のグラフのノード インデックスを使用して各部分グラフのノードにラベルを付ける方法を説明します。

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

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

グラフ ノードを各ノードが属する 2 重連結要素に基づいてビンにグループ化します。次に、各ビンをループ処理して各 2 重連結要素の部分グラフを抽出します。元のノード インデックスを使用して各部分グラフのノードにラベルを付けます。

bincell = biconncomp(G, 'OutputForm', 'cell');
n = length(bincell);

for ii = 1:n
    subplot(2,2,ii)
    plot(subgraph(G, bincell{ii}), 'NodeLabel', bincell{ii});
end

切断点の識別

グラフの切断点を識別し、グラフ プロットでそれらの点を強調表示します。

グラフを作成してプロットします。各グラフ エッジが属する 2 重連結要素を計算し、2 番目の出力を指定して切断点を識別するベクトルを返します。

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

[edgebins,iC] = biconncomp(G)

edgebins = 1×13

     4     4     4     4     4     3     3     3     3     2     1     1     1

iC = 1×3

     4     6     7

ノード 4、6 および 7 はグラフ G の切断点です。highlight を使用して iC で参照されている切断点を拡大します。

highlight(p, iC)

入力引数

G — 入力グラフ

graph オブジェクト

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

例: G = graph(1,2)

form — 出力のタイプ

'vector' (既定値) | 'cell'

出力のタイプ。次の値のいずれかとして指定します。

オプション	出力
'vector' (既定)	bins は各エッジが属する 2 重連結要素を示す数値ベクトルです。
'cell'	bins は cell 配列であり、bins{j} は要素 j に属するすべてのノードのノード ID を含みます。

出力引数

bins — 2 重連結要素

ベクトル | cell 配列

2 重連結要素。ベクトルまたは cell 配列として返されます。ビン番号は、グラフの各エッジまたはノードを 2 重連結要素に割り当てます。

• OutputForm が 'vector' (既定) の場合、bins は各エッジが属する連結要素 (ビン) を示す数値ベクトルです。自己ループであるエッジはどの 2 重連結要素にも属さないため、ビン 0 に割り当てられます。

• OutputForm が 'cell' の場合、bins は cell 配列であり、bins{j} は要素 j に属するすべてのノードのノード ID を含みます。

iC — 切断点のインデックス

ベクトル

切断点のインデックス。数値ノード ID のベクトルとして返されます。

詳細

2 重連結要素

グラフの 2 重連結要素は、極大な 2 重連結部分グラフです。切断点が一切含まれていない場合、グラフは 2 重連結です。

グラフをその 2 重連結要素に分解すると、グラフの連結状態を測定しやすくなります。連結グラフは "ブロックカット木" と呼ばれる 2 重連結要素の木に分解できます。木のブロックは共有される点で接続されており、この点が切断点です。

次の図は、以下を示しています。

• (a) 11 のノードをもつ無向グラフ。

• (b) グラフの 5 つの 2 重連結要素。元のグラフの切断点が、属する各要素において色が付けられています。

• (c) グラフのブロックカット木。各 2 重連結要素のノード (大きな円) と各切断点のノード (複数の色が付けられた小さな円) が含まれます。ブロックカット木では、エッジは各切断点を、エッジが属する各要素に連結しています。

切断点

切断点は "関節点" とも呼ばれ、削除するほど連結要素数が増えるグラフ ノードです。前の図では、切断点は複数の色をもつノード (ノード 4、6、7) です。

拡張機能

スレッドベースの環境
MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

バージョン履歴

R2016b で導入

参考

condensation | bctree | conncomp

トピック

• 有向および無向グラフ
• 幅優先探索と深さ優先探索の可視化