はじめに

約30年前に大学で習った、全域木の列挙アルゴリズムをPythonで実装してみましたので、ご紹介します。

全域木とは、元のグラフの全ての点を含む木のことです。

アルゴリズム

グラフの式表現を求めて、式表現を展開して列挙します。
例えば、三角形のグラフで各辺をそれぞれa,b,cとすると、式表現は組(abc)となり、これを展開するとab/ac/bcとなります。
グラフの式表現は以下のように求められます。
- 辺の最初の式表現として、アルファベット1文字を持たせます。
- グラフは、式表現を維持しながら辺または辺と点を削除できます。
- グラフが1点になったときに式表現が求められます。
グラフGの式表現（Expr(G))は、任意の1つの辺Eを選んで以下のように変形できます。(標準ルール)
- Expr(G) ＝和(積(組(Expr(E)), Expr(GからEを削除)), 積(Expr(E), Expr(GからEを縮約¹)))

式表現には、以下の種類があります。

和(A, B): Aの要素とBの要素の和集合です。
積(A, B): Aの要素とBの要素の積集合(組合せて文字を並べたもの)です。
組(A): Aの要素ごとに、1文字づつ消去して展開します。例えば、組(abc)は、abとacとbcの3つに展開されます。

先ほどの標準ルールだけでもできますが、計算量を減らすために、特定のケースのルールを追加します。(標準ルールから導かれます)

辺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を縮約した後のグラフについて求めます。

Pythonで実行してみる

クラス定義をします。

python3

from itertools import combinations, product
from collections import namedtuple
Union = namedtuple('Union', 'l r') # 和
Produ = namedtuple('Produ', 'l r') # 積
Combi = namedtuple('Combi', 'e') # 組
class Edge:
    def __init__(self, u, v, e):
        self.u = u
        self.v = v
        self.e = e
    def __repr__(self):
        return '<%s %s %s>'%(self.u, self.v, self.e)
class Graph:
    def __init__(self, num_nodes, edges):
        self.nodes = [[] for _ in range(num_nodes)]
        self.edges = []
        for i, (u, v) in enumerate(edges):
            self.edges.append(Edge(u, v, chr(97 + i)))
            self.nodes[u].append(i)
            self.nodes[v].append(i)
    def __repr__(self):
        return str(self.edges)
    def spanning_tree(self):
        res = Graph._reduct(self.nodes.copy(), self.edges.copy())
        return sorted(Graph._expand(res))
    @staticmethod
    def _reduct(nodes, edges):
        if not edges:
            return '' if len(nodes) == 1 else None
        for i, e in enumerate(edges): # 自己ループ
            if e.u == e.v:
                Graph._erase(nodes, edges, i)
                return Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges))
        for con in nodes: # 次数=1
            if len(con) == 1:
                e = edges[con[0]]
                Graph._erase(nodes, edges, con[0])
                return Produ(l=e.e, r=Graph._reduct(nodes, edges))
        for con in nodes: # 次数=2
            if len(con) == 2:
                e = edges[con[0]]
                edges[con[0]] = Edge(e.u, e.v, Produ(l=edges[con[0]].e,
                                                     r=edges[con[1]].e))
                Graph._shrink(nodes, edges, con[1])
                return Graph._reduct(nodes, edges)
        e = edges[0]
        nodes2, edges2 = nodes.copy(), edges.copy()
        Graph._erase(nodes, edges, 0)
        Graph._shrink(nodes2, edges2, 0)
        return Union(l=Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges)),
                     r=Produ(l=e.e, r=Graph._reduct(nodes2, edges2)))
    @staticmethod
    def _erase(nodes, edges, k):
        for a, con in enumerate(nodes):
            nodes[a] = [b if b < k else b-1 for b in con if b != k]
        del edges[k]
    @staticmethod
    def _shrink(nodes, edges, k):
        e = edges[k]
        dn = max(e.u, e.v)
        sn = e.u+e.v-dn
        nodes[sn] = nodes[sn] + nodes[dn]
        for a, con in enumerate(nodes):
            nodes[a] = [b if b < k else b-1 for b in con if b != k]
        for a, ed in enumerate(edges):
            u = sn if ed.u == dn else ed.u if ed.u < dn else ed.u-1
            v = sn if ed.v == dn else ed.v if ed.v < dn else ed.v-1
            edges[a] = Edge(u, v, ed.e)
        del edges[k]
        del nodes[dn]
    @staticmethod
    def _expand(ex):
        if ex is None:
            return set()
        elif isinstance(ex, str):
            return set(ex) if ex else {''}
        elif isinstance(ex, Combi):
            exe = Graph._expand(ex.e)
            return set.union(*(set(''.join(s) for s in
                combinations(e, len(e)-1)) for e in exe))
        exl = Graph._expand(ex.l)
        exr = Graph._expand(ex.r)
        if isinstance(ex, Union):
            return exl.union(exr)
        return {''.join(sorted((i+j))) for i, j in product(exl, exr)}

三角グラフで試してみます。

python3

g = Graph(3, [(0,1), (1,2), (2,0)])
print(g.spanning_tree())
>>>
['ab', 'ac', 'bc']

4点の完全グラフで試してみます。

python3

g = Graph(4, [(0,1), (1,2), (2,3), (3,0), (0,2), (1,3)])
print(g.spanning_tree())
>>>
['abc', 'abd', 'abf', 'acd', 'ace', 'acf', 'ade', 'aef',
 'bcd', 'bce', 'bde', 'bdf', 'bef', 'cdf', 'cef', 'def']

ちなみに、このPythonは85行ですが、Cで書くと500行で、C#で書くと330行ほどでした。

以上

辺を縮約するとは、その辺を長さ0にして、両端の点を1つに変える操作です。 ↩