最小全域木：クラスカル法とプリム法

十二の村を選び、クラスカル法を一手ずつ進めよう。66本の道路候補を短い順に調べるので、K–Lの13.89 kmはすぐに採用される。C–DとB–Cは、赤い経路ですでに両端が結ばれているため不採用となる。プリム法に切り替えると、Aから一つのネットワークが広がっていく。道路を選ぶ順序は変わり、K–Lは最後になるが、同じ二本を不採用とし、最終的には同じ11本、同じ199.04 kmに到達する。両者の根拠は共通している。カット性質だ。点を好きな二群に分けたとき、その間を結ぶ最短の道路は、どの二本の道路も同じ長さでなければ最小全域木に含まれる。その道路を除いた木を考えると、両端を結ぶ木上の経路は、どこかでカットをより長い道路によって横切らなければならない。二本を入れ替えれば、木の総延長は短くなる。プリム法では、各ステップで網掛けされたネットワークがこのようなカットの片側に当たる。次に最近傍法を選ぼう。これはプリム法の反復から、探す範囲をネットワーク全体ではなく直前に着いた村だけに変えた方法である。三手目ではD–Fの17.96 kmを選ぶが、カットを横切るA–Cは17.67 kmしかない。その後もA–Cを七回見送り、最終的な長さは10.76%余分になる。この問題を最初に解いたオタカル・ボルーフカは、南モラヴィアの電力網を念頭に1926年、「相互の距離が異なる」点について結果を述べた。これはまさに同じ条件であり、この条件のもとではクラスカル法とプリム法の答えは一致する。

湖を囲む町を選ぼう。十の町が湖の周りに並び、木は湖岸道路から一区間だけを除いた形になる。除かれるのは、JとAの間にある最も広い切れ目だ。この二つの町は直線なら25.89 kmしか離れていないが、木に沿うと128.30 km、直線距離の4.96倍になる。一方から他方へ行く経路が、ネットワークをほぼ一周するものしかないためだ。紫色の破線がこの組を示す。どの町を動かしても、新たに最大の遠回りとなる組が求められる。最小全域木が最小にするのは道路の総延長であり、任意の二つの町を結ぶ経路の長さは保証しない。25.89 kmの道路も建設すれば、AからJへは直行できる。それだけの道路を追加する価値があるかは、移動経路を考える最短経路問題である。続きはダイクストラ法のページで扱う。

三つの町を選ぼう。町どうしは40 km離れているので、全域木の長さは80.00 kmになる。中央に分岐点を置き、三本の道路を120°で交わらせると、69.28 kmで結べる。短縮率は13.40%、すなわち1 − √3/2である。正方形の四つの町では、二つの分岐点によって8.93%短くなる。三角形に戻り、CをAとBの側へ動かしてみよう。Cの角が120°を超えると分岐点はCに重なり、それ以上は分岐点を置いても短くならない。最適な分岐点を求めるのがシュタイナー木問題である。1968年、エドガー・ギルバートとヘンリー・ポラックは、正三角形が短縮率の最大例であり、平面上のどの点集合についてもシュタイナー木が最小全域木の√3/2未満にはならないと予想した。ドゥとファンは1990年に証明を発表した。しかし2010年、インナミら四人は、その証明の要となる段階が成り立たないことを示す根拠を発表した。2002年から証明の不備を指摘していたイワノフとトゥジリンも、2012年にこの予想は未解決だと記している。2025年に刊行されたシュタイナー木の未解決問題集にも、なお未解決問題として掲載されている。三角形の13.40%を超えて短縮できる点配置が存在するかどうかは、まだ分かっていない。