FindSpanningTree

FindSpanningTree[{v1,v2,…,vn}]

viの間の総距離を最小にする全域木を求める．

FindSpanningTree[g]

頂点間の総距離を最小にするグラフ g の全域木を求める．

FindSpanningTree[{g,v},…]

頂点 v を含む g の連結成分の全域木を求める．

FindSpanningTree[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細とオプション

例題

すべて開くすべて閉じる

例  (1)

グラフ中の最小全域木を求める：

全域木をハイライトする：

スコープ  (10)

FindSpanningTreeは点のリストに使うことができる：

文字列のリスト：

測地位置のリスト：

FindSpanningTreeは無向グラフに使うことができる：

有向グラフに使う：

重み付きグラフに使う：

多重グラフ：

始点となる根を持つ最小全域木を求める：

規則を使ってグラフを指定する：

FindSpanningTreeは大きいグラフに使うことができる：

一般化と拡張  (1)

最大全域木を求める：

オプション  (5)

EdgeWeight  (1)

デフォルトで，辺の重みは，あればその辺のEdgeWeight注釈，なければ1であるとみなされる：

EdgeWeight->weights を使って辺の重みを設定する：

Method  (4)

メソッドは入力によって自動的に選択される：

"Prim"を無向密グラフに使うことができる：

"Kruskal"を無向疎グラフに使うことができる：

"MinimumCostArborescence"を有向グラフに使うことができる：

アプリケーション  (7)

ある企業がシカゴの周辺地区数ヶ所を結ぶファイバー回路網を計画している．この会社は特定の経路についてのみ敷設権を所有している．これらの経路の中には他より費用がかかることが見込まれるものもある．すべての周辺地区を結び，総費用が最低となる連結経路の部分グラフを求める：

電話会社が戸数10戸の村に電話線を引くことになった．各ノードは家で各家にはその場所がある．電話線を最小にして全戸を繋ぐ方法を求める：

結果の電話線の総延長：

行の項が数ヶ所を除いてほぼ等しい二次元配列がある． は行 および の異なる項の数を表す．この配列は，完全な行1行と，別の行と異なる項としての他の行すべてを表すことによって，保存することができる．配列の各行を，他のすべての頂点への辺を持ち，異なる項の数を表す重み の頂点としてモデル化することができる．最小重み全域木を使って効率的な保存スキームを求める：

行1を完全に保存し，残りの行については親と異なる位置と項のみを保存する：

アフリカ諸国すべての地理的中心を繋ぐ国家間幹線道路システムを建設する：

全諸国間の総距離を最小化する：

幹線道路を示す：

ランダムな重みを持つ格子グラフから迷路を生成する：

最小全域木：

迷路にカスタムのスタイリングを施す：

迷路グラフ：

一様ランダム重みのある完全グラフの最小全域木の，期待される大きさを求める：

全域木の大きさは，その全域木の辺重みの合計として与えられる：

大きい完全グラフでは，期待される大きさが TemplateBox[{3}, Zeta]に近くなる：

ヨーロッパ諸国を訪れるための最小全域木を求める：

諸国間の経路を可視化する：

特性と関係  (2)

全域木グラフをは木である：

BreadthFirstScanを使ってグラフの全域木を求めることができる：

DepthFirstScanを使って全域木を求める：

考えられる問題  (1)

非連結グラフについては，各連結成分ごとの全域木が与えられる：

全域木をハイライトする：

おもしろい例題  (1)

頂点が球上にあり一様分布に従うランダムグラフの最小全域木：

Wolfram Research (2014), FindSpanningTree, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindSpanningTree.html （2021年に更新）.

テキスト

Wolfram Research (2014), FindSpanningTree, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindSpanningTree.html （2021年に更新）.

CMS

Wolfram Language. 2014. "FindSpanningTree." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2021. https://reference.wolfram.com/language/ref/FindSpanningTree.html.

APA

Wolfram Language. (2014). FindSpanningTree. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindSpanningTree.html

BibTeX

@misc{reference.wolfram_2024_findspanningtree, author="Wolfram Research", title="{FindSpanningTree}", year="2021", howpublished="\url{https://reference.wolfram.com/language/ref/FindSpanningTree.html}", note=[Accessed: 21-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_findspanningtree, organization={Wolfram Research}, title={FindSpanningTree}, year={2021}, url={https://reference.wolfram.com/language/ref/FindSpanningTree.html}, note=[Accessed: 21-November-2024 ]}