bctree

ブロックカット木グラフ

構文

tree = bctree(G)

[tree,ind] = bctree(G)

説明

tree = bctree(G) はグラフ G のブロックカット木を返します。tree 内の各ノードは G の 2 重連結要素または切断点を表します。切断点を表すノードは、その切断点を含む 2 連結要素を表すすべてのノードに連結しています。

[tree,ind] = bctree(G) は G のノードを tree のノードにマッピングする数値ノード インデックスのベクトルも返します。

例

グラフのブロックカット木の計算

グラフのブロックカット木を計算し、結果のノード プロパティを表示してグラフ プロットで切断点を強調表示します。

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

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 になります。

入力引数

G — 入力グラフ

graph オブジェクト

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

例: G = graph(1,2)

出力引数

tree — ブロックカット木グラフ

graph オブジェクト

ブロックカット木グラフ。graph オブジェクトとして返されます。tree には、G の各切断点のノードと G の各 2 重連結要素のノードが含まれます。ノード テーブル tree.Nodes には、各ノードが何を表すかを説明する追加ノード属性が含まれます。

• tree.Nodes.IsComponent(i) — ノード i が 2 重連結要素を表す場合、logical 1 (true) と等しい値。それ以外の場合、値は logical 0 (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 で導入

参考

biconncomp | condensation

トピック

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