全域木

各辺に重み（コスト）がある場合、最小の総和コストで構成される全域木を最小全域木という。

• クラスカル法 - 単純な貪欲法で計算量は ${\displaystyle O(E\log {E})}$。
• プリム法 - 貪欲法だが計算量は ${\displaystyle O(E+V\log {V})}$。辺の数が頂点に比べて十分大きいときは ${\displaystyle O(E)}$ と見なせる。
• ブルーフカ法 - 貪欲法で、計算量は ${\displaystyle O(E\log {V})}$。

辺の重みが均一の場合は幅優先探索で ${\displaystyle O(E)}$ で求まる。

import collections
import matplotlib.pyplot as plt
import networkx as nx

def bfs(G):
    """グラフGの最小全域木Tを返す関数"""
    V = [v for v in G.nodes()]
    Q = collections.deque([V[0]])
    explored = {v: False for v in G.nodes()}
    explored[V[0]] = True
    T_edges = []  # Tに含まれる辺に対応するtupleを記録するlist
    while len(Q) != 0:
        v = Q.popleft()
        unexplored_neighbors = [i for i in G.neighbors(v) if not explored[i]]
        for i in unexplored_neighbors:
            Q.append(i)
            T_edges += [(v, i)]  # iに初めて到達した場合に限り辺をlistに加える
            explored[i] = True
    return G.edge_subgraph(T_edges).copy()  # Gの部分グラフとしてTを返す

# グリッド描画
G = nx.grid_2d_graph(4, 3)
p = {v: v for v in G.nodes()}
nx.draw_networkx(G, pos=p, node_color='lightgray', node_size=1300, with_labels=True)
plt.axis('off')
plt.show()

# 幅優先探索による探索結果描画
bfst = bfs(G)
DG = nx.DiGraph()
DG.add_edges_from(bfst.edges())
nx.draw_networkx(DG, edgelist=bfst.edges(), pos=p, node_color='lightgray', node_size=1500, with_labels=True)
plt.axis('off')
plt.show()

ある頂点から他の頂点への移動コストが最小になるような経路を求める問題を最短経路問題という。ある頂点から他の全ての頂点に移動するコストが最小になる木のことを最短経路木といい、これは全域木である。最短経路問題は単一の頂点から任意の頂点への最短経路木を求める方法としてはダイクストラ法やベルマン-フォード法などが、また任意の頂点から任意の頂点への移動コストが最小になるような最短経路木を求める方法としてはワーシャル-フロイド法が知られている。

全域木の概念は特にコンピュータネットワーク関連で重要な位置を占めている。何故なら各種端末やルータ、スイッチングハブなどを頂点と見なし、接続されているケーブル類を辺と見なせばネットワークはひとつの巨大なグラフであり、全域木の概念はそのグラフに対する経路の構築手順であると見なせるからである。実際にOSPFやSTPでは上記の最短経路木を構成することによって通信経路を決定している。

全域木を用いることにより、結び目理論における結び目の射影図を簡単に構成する方法が報告されている^[1]。この方法によれば、結び目の交点数には制限がなく、任意の交点数で射影図を構成できる。具体的には、一般的な結び目の射影図に対して、2重性並行表示と呼ばれる特殊な射影図を定義する。この2重性並行表示は、3-正則平面グラフと対応がとれる。これにより、どの様な結び目も、3-正則平面グラフで表現できることになる。結び目を構成する方法は、3-正則平面グラフの全域木と双対グラフの全域木を用いる。その概略は、3-正則平面グラフの任意の全域木の各辺に「偶数個の交点」を配置し、全域木の辺ではない 3-正則平面グラフの各辺には「奇数個の交点」を配置する．この操作で得られた射影図は結び目である、という結論が記述されている^[2]。