スパニングツリー
全域木を全列挙するプログラムを見直して、アルゴリズムを思い出したので、書いておく。
目的はグラフから全域木を全列挙すること。
そのためには、グラフの式表現を求め、式表現を展開する。
例えば、三角形のグラフで各辺をそれぞれa,b,cとすると、式表現は[abc]となり、これを展開するとab/ac/bcとなる。
グラフの式表現は以下のように求められる。まず、辺に式表現を持つようにする。辺の最初の式表現は、アルファベット1文字としよう。
グラフは、式表現を維持しながら辺または辺と点を削除できる。このようにして、グラフが1点になったときに式表現が求められる。
グラフGの式表現（Expr(G))は、任意の1つの辺Eを選んで以下のように変形できる。
Eを取り除くと、非連結になる場合：Expr(G)＝Expr(E)Expr(GからEを縮約)
非連結にならない場合：Expr(G)＝([Expr(E)]Expr(GからEを削除)+Expr(E)Expr(GからEを縮約))
辺を縮約とはその辺を長さ0にして、両端の点を1つに変える操作である。式表現には、以下の種類がある。
- (A+B)：展開するとAの展開リストにBの展開リストが追加される形となる。尚、展開した結果が同一であれば片方を削除する。
- AB：展開するとAの展開リストとBの展開リストを組合せて文字を並べたものとなる。
- [AB]：ABの展開リストの要素ごとに、1文字づつ消去して展開をさらに行う。例えば、[abc]は、abとacとbcの3つに展開される。
さて、最初のルールだけでもできるが、大変なので特殊ケース用のルールも書いてみよう。 (最初のルールと同義である)
- 辺Eと辺Fが(同一の点どうしをつないでいる)多重辺の場合：Expr(E)←(Expr(E)+Expr(F))として、辺Fを削除した後のグラフについて求める。
- 辺Eが自己ループの場合：Expr(G)=[Expr(E)]Expr(GからEを削除)
- 辺Eの片方の端点の次数(接続する辺の数)=1の場合：Expr(G)=Expr(E)Expr(GからEを縮約))
- 上記のルールを適用すれば、残りのどの辺を削除しても非連結とならない。
- 辺Eと辺Fが点Vで接続しており、点Vの次数=2の場合：Expr(E)←Expr(E)Expr(F)として、辺Fを縮約した後のグラフについて求める。
例として4点の完全グラフの場合、式表現は(([afce]+d[af][ce])+b[(a+e)d(c+f)])、展開すると afc/afe/ace/fce/dac/dae/dfc/dfe/bad/bac/bdc/baf/bdf/bed/bec/befとなる。
Cのプログラムは500行で、C#では330行ほどであった。
