ドキュメンテーション

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

minspantree

グラフの最小全域木

構文

T = minspantree(G)
T = minspantree(G,Name,Value)
[T,pred] = minspantree(___)

説明

T = minspantree(G) は、グラフ G最小全域木 T を返します。

T = minspantree(G,Name,Value) は、1 つ以上の名前と値のペアの引数で指定された追加のオプションを使用します。たとえば、minspantree(G,'Method','sparse') は最小全域木の計算にクラスカル アルゴリズムを使用します。

[T,pred] = minspantree(___) は、前述の構文に示した任意の入力引数を使用して、先行ノードのベクトル pred も返します。

すべて折りたたむ

重み付きエッジをもつ立方体グラフを作成し、プロットします。

s = [1 1 1 2 5 3 6 4 7 8 8 8];
t = [2 3 4 5 3 6 4 7 2 6 7 5];
weights = [100 10 10 10 10 20 10 30 50 10 70 10];
G = graph(s,t,weights);
p = plot(G,'EdgeLabel',G.Edges.Weight);

グラフの最小全域木を計算し、そのグラフの上にプロットします。TG と同じノードを含みますが、エッジは一部が含まれます。

[T,pred] = minspantree(G);
highlight(p,T)

複数の要素をもつグラフを作成し、プロットします。

s = {'a' 'a' 'a' 'b' 'b' 'c' 'e' 'e' 'f' 'f' 'f' 'f' 'g' 'g'};
t = {'b' 'c' 'd' 'c' 'd' 'd' 'f' 'g' 'g' 'h' 'i' 'j' 'i' 'j'};
G = graph(s,t);
p = plot(G,'Layout','layered');

ノード i から開始して、グラフの最小全域森を求めます。得られた森をプロット内で強調表示します。グラフ ノード名は最小全域木グラフに引き継がれます。

[T,pred] = minspantree(G,'Type','forest','Root',findnode(G,'i'));
highlight(p,T)

先行ノードのベクトル pred を使用して、最小全域森の有向バージョンを作成します。この木のすべてのエッジは、各要素のルート ノード (ノード i および a) から遠ざかる方向を向きます。

rootedTree = digraph(pred(pred~=0),find(pred~=0),[],G.Nodes.Name);
plot(rootedTree)

入力引数

すべて折りたたむ

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

例: G = graph(1,2)

名前と値のペアの引数

オプションの Name,Value の引数ペアをコンマ区切りで指定します。Name は引数名で、Value は対応する値です。Name は引用符で囲まなければなりません。Name1,Value1,...,NameN,ValueN のように、複数の名前と値のペアの引数を任意の順序で指定できます。

例: [T,pred] = minspantree(G,'Method','sparse')

最小全域木アルゴリズム。'Method' と、次の表のいずれかのオプションで構成されるコンマ区切りのペアとして指定します。

オプション説明
'dense' (既定)プリムのアルゴリズム。このアルゴリズムはルート ノードから開始し、グラフを通過しながら木にエッジを追加します。
'sparse'クラスカルのアルゴリズム。このアルゴリズムは重みを基準にしてすべてのエッジを並べ替え、エッジが循環を作成しない場合にそのエッジを木に追加します。

ルート ノード。'Root'、およびノード インデックスまたはノード名で構成されるコンマ区切りのペアとして指定します。既定のルート ノードは 1 です。

  • 'Method''dense' (既定) の場合、ルート ノードは開始ノードです。

  • 'Method''sparse' の場合、ルート ノードは先行ノードのベクトル pred の計算にのみ使用されます。

ルート ノードは次のいずれかの形式で指定できます。

スカラー ノード インデックス1
文字ベクトルのノード名'A'
string スカラーのノード名"A"

最小全域木のタイプ。'Type' と、次の表のいずれかのオプションで構成されるコンマ区切りのペアとして指定します。

オプション説明
'tree'

単一の木のみが返されます。木はルート ノードを含みます。

'forest'

最小全域木の森が返されます。つまり、'forest' を指定すると、グラフ内のすべての連結要素の最小全域木が計算されます。

出力引数

すべて折りたたむ

最小全域木。graph オブジェクトとして返されます。

先行ノード。ノード インデックスのベクトルとして返されます。pred(I) は先行ノード I のノード インデックスです。慣例により、pred(rootNode) = 0 です。Type'tree' の場合、ルート ノードと同じ要素内にないすべてのノード I について pred(I) = NaN です。

pred は、最小全域木の指向バージョンを指定します。すべてのエッジがルート ノードから遠ざかる方向を向きます。

詳細

すべて折りたたむ

最小全域木

連結グラフの場合、全域木はグラフの各ノードを連結し、循環を含まない部分グラフです。任意のグラフについて、多くの全域木が存在します。各エッジに重みを割り当てることにより、異なる全域木にエッジの合計重みを示す値が割り当てられます。そして、最小全域木は、エッジの合計重みが最小の全域木です。

重みが等しいエッジからなるグラフでは、すべての全域木が最小全域木になります。これは、n 個のノードを通過するには n-1 本のエッジが必要だからです。

R2015b で導入