シュタイナー木

シュタイナー木（Steiner tree）

シュタイナー木は、グラフ理論および組合せ最適化における fundamental な概念です。特に、通信ネットワーク、交通網、電子回路の配線など、様々なシステムにおいて特定の複数地点間を最も効率的に接続する構造を設計する際に重要な役割を果たします。

定義

まず、無向グラフG = (V, E) が与えられたとします。Vは頂点（ノード）の集合、Eは辺（エッジ）の集合です。さらに、Vの部分集合として、あらかじめ指定された頂点の集合Tが存在します。このTをターミナル集合と呼びます。

シュタイナー木とは、このターミナル集合Tに含まれる全ての頂点をグラフGの中で相互に連結するような、Gの部分グラフであって木構造を持つものです。シュタイナー木は、ターミナル集合Tに含まれない頂点（シュタイナー点または非ターミナル）を連結のために含んでいても構いません。

全域木との関連

シュタイナー木の定義から、特別なケースとして全域木（Spanning tree）との関係が分かります。もしターミナル集合TがグラフGの全ての頂点集合Vと一致する（T = V）場合、シュタイナー木はGの全ての頂点を連結する木構造となります。これは全域木の定義そのものです。したがって、T=Vの場合、シュタイナー木はグラフGの全域木と一致します。

最小シュタイナー木とシュタイナー問題

多くの応用では、連結構造の「コスト」を最小化したいと考えます。グラフの各辺に、距離やコストといった正の重みが割り当てられている場合を考えましょう。

この重み付きグラフにおいて、与えられたターミナル集合Tの全ての頂点を連結するシュタイナー木の中で、それを構成する全ての辺の重みの総和が最も小さくなるものを最小シュタイナー木（Minimum Steiner tree）と呼びます。

この最小シュタイナー木を求める問題は、一般にシュタイナー問題と呼ばれ、最短連結問題や最短ネットワーク問題とも称されます。

計算の困難性：NP困難

シュタイナー問題は、計算機科学においてNP困難（NP-hard）な問題クラスに属することが知られています。これは、問題の規模が大きくなるにつれて、最適な解を効率的に（すなわち多項式時間で）見つけるアルゴリズムが存在しない可能性が極めて高いことを意味します。NP困難な問題は、大規模なインスタンスに対して計算時間が指数関数的に増加し、現実的な時間での厳密解探索が困難になる場合が多いです。シュタイナー問題がNP困難であるのは、ターミナル以外のシュタイナー点をどこに配置するかという自由度と、その組み合わせの爆発に起因すると考えられます。

シュタイナー木アルゴリズム

NP困難であるシュタイナー問題を解くために、様々なアルゴリズムが研究開発されています。これらを総称してシュタイナー木アルゴリズムと呼びます。

最適な解を厳密に求めるアルゴリズムとしては、動的計画法を用いるDreyfus–Wagner法などが知られています。しかし、これらの正確なアルゴリズムは計算量が大きいため、大規模問題に対しては近似アルゴリズムやヒューリスティック手法が実用的に用いられます。これらは最適解を保証しない代わりに、比較的短時間で「良い」解を見つけ出します。

関連するグラフ理論の問題

シュタイナー問題は、他の有名なグラフ理論の最適化問題と関連しつつも、異なる性質を持ちます。

全域木問題（Spanning Tree Problem）: グラフ全体の全ての頂点を連結する木。最小全域木（MST）はクラスカル法などで効率的に解けます。シュタイナー問題は、T=Vの時にMST問題と一致しますが、通常は特定のターミナルのみを対象とします。
最短経路問題（Shortest Path Problem）: 特定の二点間の最小コストのパス。ダイクストラ法などで効率的に解けます。シュタイナー問題は複数の点を連結する木構造を求めます。
最小全域木問題（Minimum Spanning Tree Problem）: グラフ全体の全域木の中で辺重み総和が最小のもの。シュタイナー問題は、対象がターミナル集合であり、シュタイナー点を含みうる点で異なります。
巡回セールスマン問題（TSP）: 全ての点を訪れて出発点に戻る最短の閉路。NP困難ですが、連結構造が閉路である点が異なります。
頂点被覆問題（Vertex Cover Problem）: 全ての辺をカバーする最小サイズの頂点集合。NP困難です。
最大クリーク問題（Maximum Clique Problem）: 最大サイズの完全部分グラフ。NP困難です。
* 最大流最小カット定理: ネットワークフローに関する定理であり、連結構造そのものを求める問題とは異なります。

シュタイナー問題は、これらの問題と比較することで、その独特な性質と計算困難性が理解されます。

まとめ

シュタイナー木、特に最小シュタイナー木を求めるシュタイナー問題は、グラフ中の特定の頂点群を最小コストで連結する構造を見つけ出す重要な問題です。NP困難であるため大規模問題の厳密解探索は困難ですが、様々なアルゴリズムが研究されており、ネットワーク最適化など幅広い分野で応用されています。

もう一度検索