全域木

グラフ理論における全域木（スパニングツリー）

グラフ理論において、全域木（ぜんいきぎ、英: Spanning tree）とは、グラフの全頂点を含む部分グラフであり、かつ木構造（連結で閉路を持たないグラフ）であるものを指します。全域木は、連結グラフに必ず存在し、非連結グラフには存在しません。

全域木の定義と特徴

全域部分グラフ: グラフのすべての頂点を含む部分グラフ。
木構造: 連結であり、閉路（サイクル）を含まないグラフ。
存在条件: 連結グラフには必ず存在し、非連結グラフには存在しない。

最小全域木

グラフの各辺に重み（コスト）が与えられている場合、全域木の中で辺の重みの総和が最小になるものを最小全域木といいます。

最小全域木を求めるアルゴリズム

クラスカル法:
単純な貪欲法に基づき、計算量は \( O(E \log E) \) です。ここで、\( E \) はグラフの辺の数を表します。
プリム法:
貪欲法の一種で、計算量は \( O(E + V \log V) \) です。ここで、\( V \) はグラフの頂点の数を表します。
辺の数が頂点数に比べて十分大きい場合は、計算量を \( O(E) \) とみなすことができます。

辺の重みが均一な場合:
幅優先探索（BFS）を用いることで、計算量 \( O(E) \) で最小全域木を求めることができます。

最短経路問題と最短経路木

ある頂点から他の頂点への移動コストが最小となる経路を求める問題を最短経路問題といい、この問題を解くことで得られる、ある頂点から他のすべての頂点への移動コストが最小となる木を最短経路木といいます。最短経路木は全域木の一種です。

最短経路問題を解くためのアルゴリズム

ダイクストラ法:
単一の始点から他のすべての頂点への最短経路を求めます。
ベルマン-フォード法:
単一の始点から他のすべての頂点への最短経路を求めます。負の重みを持つ辺がある場合でも使用可能です。
ワーシャル-フロイド法:
任意の頂点間すべての最短経路を求めます。

全域木の応用

全域木の概念は、特にコンピュータネットワークの分野で重要な役割を果たしています。ネットワーク内の各端末やルータ、スイッチングハブなどをグラフの頂点、それらを接続するケーブルを辺と見なすことで、ネットワーク全体をグラフとして捉えることができます。全域木は、このグラフにおける経路構築手順と見なすことができ、実際にOSPFやSTPなどのプロトコルで通信経路を決定するために活用されています。

具体的な応用例

ネットワークルーティング: OSPFやSTPは、最短経路木を構成することで最適な通信経路を決定します。

結び目理論における全域木

全域木は、結び目理論における結び目の射影図を構成する際にも利用されています。結び目の射影図は、結び目を平面に射影した図のことで、全域木を用いることで、任意の交点数を持つ射影図を容易に作成することが可能です。

結び目の射影図構成の手順

1. 2重性並行表示: 結び目の射影図に対して、特殊な射影図である2重性並行表示を定義します。これは3-正則平面グラフと対応します。
2. 3-正則平面グラフ: どのような結び目も、3-正則平面グラフで表現できます。
3. 全域木と双対グラフ: 3-正則平面グラフの全域木と、その双対グラフの全域木を利用します。
4. 交点の配置: 全域木の各辺に偶数個の交点を、全域木にない辺には奇数個の交点を配置することで、結び目の射影図を構成します。

まとめ

全域木は、グラフ理論における基本的な概念であり、様々な分野で応用されています。特に、ネットワークや結び目理論など、その応用範囲は多岐にわたります。全域木を理解することで、複雑な問題をより効率的に解決するための知見を得ることができます。

参考文献

グラフ理論に関する書籍や論文
ネットワークに関する教科書や資料

関連項目

スパニングツリープロトコル
シュタイナー木
グラフ理論
交点数 (結び目理論)
結び目理論
* タングル

もう一度検索