Pythonで特定のグラフから特別なタイプのサブグラフを見つけるプログラム

ここでは、「ヘッド(head)」と「フィート(feet)」という2種類の頂点を持つ特殊なグラフを考えます。このグラフにはヘッドがちょうど1つだけ存在し、k本の辺によってヘッドがそれぞれのフィートへ接続されています。

入力として無向・非重み付きグラフが与えられたとき、そのグラフの頂点素な部分グラフ(vertex disjoint subgraph)の中から、こうした特殊なグラフを見つけ出します。2つのグラフが「頂点素」であるとは、互いに共通の頂点を1つも持たないことを意味します。

たとえば、次のようなグラフが与えられたとします。

ノード数(n)= 6、フィート数(t)= 2 の場合、出力は 5 になります。つまり、与えられたグラフの頂点素な部分グラフの中には、条件を満たす特殊なグラフが5つ存在しうるということです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• G := n+1個の空リストを格納した新しいリスト(隣接リスト)を作成する
• edges の各要素について以下を行う
  • s := item[0]、d := item[1]
  • G[s] の末尾に d を挿入する
  • G[d] の末尾に s を挿入する
• visit := 新しいマップ(辞書)を作成する
• i を 0 から n までループし、以下を行う
  • v := G[i]
  • v のサイズが 1 の場合(次数1の頂点=フィート候補)
    • s := v[0](唯一の隣接頂点=ヘッド候補)
    • s が visit に存在しない場合は visit[s] := [i] とする
    • 存在する場合は visit[s] の末尾に i を追加する
  • そうでなく v のサイズが 0 の場合(孤立頂点)は n := n - 1 とする
• tmp := 0 とする
• visit の各キー k について以下を行う
  • x := visit[k] のサイズ − t
  • x > 0 であれば tmp := tmp + x とする
• n − tmp を返す

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(n, t, edges):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        s, d = map(int, item)
        G[s].append(d)
        G[d].append(s)
    visit = {}
    for i in range(n):
        v = G[i]
        if len(v) == 1:
            s = v[0]
            if s not in visit:
                visit[s] = [i]
            else: visit[s].append(i)
        elif len(v) == 0:
            n -= 1
    tmp = 0
    for k in visit:
        x = len(visit[k])-t
        if x > 0:
            tmp += x
    return n - tmp

print(solve(6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]))

入力

6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]

出力

5

処理のポイント

このアルゴリズムの鍵となるのは、次数(degree)に着目した頂点の分類です。

• 次数1の頂点:他の頂点と1本の辺だけでつながっているため、フィート(葉)の候補になります。その唯一の隣接頂点がヘッドの候補となります。
• 次数0の頂点:どの辺にも接続されていない孤立頂点なので、カウント対象から除外します(n を減らします)。
• visit 辞書:同じヘッド候補にぶら下がるフィート同士をグループ化して記録します。

最後に、各グループのフィート数から t を引いた値(x)が正であれば、その分だけ余剰として tmp に加算し、有効なノード数 n から差し引いた結果を返します。これにより、与えられたグラフから条件を満たす特殊なサブグラフの数を効率よく求めることができます。