MATLAB ヘルプ センター
グラフの 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
G
例
bins = biconncomp(G,'OutputForm',form) は、form が 'cell' のときに出力を cell 配列として返します。bins{j} には要素 j のすべてのノードのノード ID が含まれます。form の既定値は 'vector' です。
form
'cell'
bins{j}
j
'vector'
[bins,iC] = biconncomp(___) はさらにどのノードが切断点 (関節点とも呼ばれる) であるかを示すノード インデックス iC も返します。
iC
すべて折りたたむ
グラフを作成してプロットします。各エッジの属する 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 重連結要素を部分グラフとして抽出する方法と元のグラフのノード インデックスを使用して各部分グラフのノードにラベルを付ける方法を説明します。
グラフを作成してプロットします。
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
highlight(p, iC)
graph
入力グラフ。graph オブジェクトとして指定します。無向グラフ オブジェクトを作成するには、graph を使用します。
例: G = graph(1,2)
G = graph(1,2)
出力のタイプ。次の値のいずれかとして指定します。
2 重連結要素。ベクトルまたは cell 配列として返されます。ビン番号は、グラフの各エッジまたはノードを 2 重連結要素に割り当てます。
OutputForm が 'vector' (既定) の場合、bins は各エッジが属する連結要素 (ビン) を示す数値ベクトルです。自己ループであるエッジはどの 2 重連結要素にも属さないため、ビン 0 に割り当てられます。
OutputForm
0
OutputForm が 'cell' の場合、bins は cell 配列であり、bins{j} は要素 j に属するすべてのノードのノード ID を含みます。
切断点のインデックス。数値ノード ID のベクトルとして返されます。
グラフの 2 重連結要素は、極大な 2 重連結部分グラフです。切断点が一切含まれていない場合、グラフは 2 重連結です。
グラフをその 2 重連結要素に分解すると、グラフの連結状態を測定しやすくなります。連結グラフは "ブロックカット木" と呼ばれる 2 重連結要素の木に分解できます。木のブロックは共有される点で接続されており、この点が切断点です。
次の図は、以下を示しています。
(a) 11 のノードをもつ無向グラフ。
(b) グラフの 5 つの 2 重連結要素。元のグラフの切断点が、属する各要素において色が付けられています。
(c) グラフのブロックカット木。各 2 重連結要素のノード (大きな円) と各切断点のノード (複数の色が付けられた小さな円) が含まれます。ブロックカット木では、エッジは各切断点を、エッジが属する各要素に連結しています。
切断点は "関節点" とも呼ばれ、削除するほど連結要素数が増えるグラフ ノードです。前の図では、切断点は複数の色をもつノード (ノード 4、6、7) です。
すべて展開する
backgroundPool
ThreadPool
R2016b で導入
condensation | bctree | conncomp
condensation
bctree
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 のサイトは、お客様の地域からのアクセスが最適化されていません。
南北アメリカ
ヨーロッパ
アジア太平洋地域
最寄りの営業オフィスへのお問い合わせ