ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

bctree

ブロックカット木グラフ

構文

tree = bctree(G)
[tree,ind] = bctree(G)

説明

tree = bctree(G) はグラフ G のブロックカット木を返します。tree 内の各ノードは G2 重連結要素または切断点を表します。切断点を表すノードは、その切断点を含む 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 になります。

入力引数

すべて折りたたむ

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

例: G = graph(1,2)

出力引数

すべて折りたたむ

ブロックカット木グラフ。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(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) です。

R2016b で導入