全域木
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/06/11 21:45 UTC 版)
最小全域木
各辺に重み(コスト)がある場合、最小の総和コストで構成される全域木を最小全域木という。
辺の重みが均一の場合は幅優先探索で で求まる。
最短経路問題
ある頂点から他の頂点への移動コストが最小になるような経路を求める問題を最短経路問題という。ある頂点から他の全ての頂点に移動するコストが最小になる木のことを最短経路木といい、これは全域木である。最短経路問題は単一の頂点から任意の頂点への最短経路木を求める方法としてはダイクストラ法やベルマン-フォード法などが、また任意の頂点から任意の頂点への移動コストが最小になるような最短経路木を求める方法としてはワーシャル-フロイド法が知られている。
応用
全域木の概念は特にコンピュータネットワーク関連で重要な位置を占めている。何故なら各種端末やルータ、スイッチングハブなどを頂点と見なし、接続されているケーブル類を辺と見なせばネットワークはひとつの巨大なグラフであり、全域木の概念はそのグラフに対する経路の構築手順であると見なせるからである。実際にOSPFやSTPでは上記の最短経路木を構成することによって通信経路を決定している。
- ^ 長島 隆廣『3-正則平面グラフを用いた結び目の構成に関する定理』日本数学協会論文集・別冊数学文化・第2号,2006年12月発行,日本数学協会,pp.52-79.
- ^ 長島 隆廣『3-正則平面グラフを用いた結び目の構成に関する定理』論文PDF:https://researchmap.jp/T_Nagashima/ または, https://researchmap.jp/multidatabases/multidatabase_contents/detail/263160/b962b603f071c834290b5e34bfdd70cd?frame_id=539358
- 全域木のページへのリンク