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: [6x1 table] Nodes: [7x3 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 になります。
入力引数
出力引数
tree
— ブロックカット木グラフ
graph
オブジェクト
ブロックカット木グラフ。graph
オブジェクトとして返されます。tree
には、G
の各切断点のノードと G
の各 2 重連結要素のノードが含まれます。ノード テーブル tree.Nodes
には、各ノードが何を表すかを説明する追加ノード属性が含まれます。
tree.Nodes.IsComponent(i)
— ノードi
が 2 重連結要素を表す場合、logical1
(true
) と等しい値。それ以外の場合、値は logical0
(false
) と等しくなります。tree.Nodes.ComponentIndex(i)
— ノードi
で表される要素を示すインデックス。ノードi
が切断点を表す場合、値はゼロです。tree.Nodes.CutVertexIndex(i)
— ノードi
で表される切断点を示すインデックス。ノードi
が 2 重連結要素を表す場合、値はゼロです。
ind
— ノード インデックス
ベクトル
ノード インデックス。数値ベクトルとして返されます。ind(i)
は、入力グラフ G
のノード i
を表す出力グラフ tree
のノードです。
ノード
i
がグラフG
の切断点の場合、ind(i)
はtree
の関連ノードです。ノード
i
が切断点ではないがグラフG
の 2 重連結要素のいずれかに属している場合、ind(i)
はその 2 重連結要素を表すtree
のノードです。ノード
i
がグラフG
の孤立ノードの場合、ind(i)
はゼロです。
詳細
2 重連結要素
グラフの 2 重連結要素は、極大な 2 重連結部分グラフです。切断点が一切含まれていない場合、グラフは 2 重連結です。
グラフをその 2 重連結要素に分解すると、グラフの連結状態を測定しやすくなります。連結グラフは "ブロックカット木" と呼ばれる 2 重連結要素の木に分解できます。木のブロックは共有される点で接続されており、この点が切断点です。
次の図は、以下を示しています。
(a) 11 のノードをもつ無向グラフ。
(b) グラフの 5 つの 2 重連結要素。元のグラフの切断点が、属する各要素において色が付けられています。
(c) グラフのブロックカット木。各 2 重連結要素のノード (大きな円) と各切断点のノード (複数の色が付けられた小さな円) が含まれます。ブロックカット木では、エッジは各切断点を、エッジが属する各要素に連結しています。
切断点
切断点は "関節点" とも呼ばれ、削除するほど連結要素数が増えるグラフ ノードです。前の図では、切断点は複数の色をもつノード (ノード 4、6、7) です。
拡張機能
スレッドベースの環境
MATLAB® の backgroundPool
を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool
を使用してコードを高速化します。
バージョン履歴
R2016b で導入
MATLAB コマンド
次の MATLAB コマンドに対応するリンクがクリックされました。
コマンドを MATLAB コマンド ウィンドウに入力して実行してください。Web ブラウザーは MATLAB コマンドをサポートしていません。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)