bctree
ブロックカット木グラフ
説明
例
グラフのブロックカット木を計算し、結果のノード プロパティを表示してグラフ プロットで切断点を強調表示します。
グラフを作成してプロットします。
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);
グラフのブロックカット木を計算してノード プロパティを表示します。
tree = bctree(G); tree.Nodes
ans=7×3 table
IsComponent ComponentIndex CutVertexIndex
___________ ______________ ______________
true 1 0
true 2 0
true 3 0
true 4 0
false 0 4
false 0 6
false 0 7
切断点を表すノードの赤い菱形のマーカーを使ってブロックカット木をプロットします。円形ノードは元のグラフの 2 重連結要素を表します。
p2 = plot(tree,'MarkerSize',9); highlight(p2,5:7,'Marker','d','NodeColor','r')
グラフを作成してプロットします。
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);
グラフのブロックカット木 tr を計算し、ノード インデックスを返す 2 番目の出力 ix を指定します。
[tr,ix] = bctree(G)
tr =
graph with properties:
Edges: [6×1 table]
Nodes: [7×3 table]
ix = 1×10
4 4 4 5 3 6 7 1 1 2
各インデックス ix(j) は、入力グラフのノード j を表すブロックカット木のノードを示します。たとえば、tr のノード 4 はノード 1、2 および 3 を含む G の要素を表すため、ix の最初の 3 つのエントリはすべて 4 になります。
入力引数
出力引数
詳細
グラフの 2 重連結要素は、極大な 2 重連結部分グラフです。切断点が一切含まれていない場合、グラフは 2 重連結です。
グラフをその 2 重連結要素に分解すると、グラフの連結状態を測定しやすくなります。連結グラフは "ブロックカット木" と呼ばれる 2 重連結要素の木に分解できます。木のブロックは共有される点で接続されており、この点が切断点です。
次の図は、以下を示しています。
(a) 11 のノードをもつ無向グラフ。
(b) グラフの 5 つの 2 重連結要素。元のグラフの切断点が、属する各要素において色が付けられています。
(c) グラフのブロックカット木。各 2 重連結要素のノード (大きな円) と各切断点のノード (複数の色が付けられた小さな円) が含まれます。ブロックカット木では、エッジは各切断点を、エッジが属する各要素に連結しています。
拡張機能
バージョン履歴
R2016b で導入
