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

頭と足という名前の2つのタイプの頂点を持つ特別なタイプのグラフがあるとします。グラフにはヘッドが1つだけあり、ヘッドを各足に接続するk個のエッジがあります。したがって、無向、無加重のグラフが与えられた場合、グラフの頂点が互いに素なサブグラフで、これらの特殊なタイプのグラフを見つける必要があります。共通の頂点がない場合、2つのグラフは頂点が互いに素であると言われます。

したがって、入力が次のような場合

ノード数（n）=5、フィート数（t）=2の場合、出力は5になります。

与えられたグラフの頂点が互いに素なサブグラフであるそのような特別なグラフが5つある可能性があります。

これを解決するには、次の手順に従います-

• G：=n+1個の空のリストを含む新しいリスト
• エッジの各アイテムについて、
  • s：=item [0]
  • d：=item [1]
  • G[s]の最後にdを挿入
  • G [d]
  の最後にsを挿入します
• 訪問：=新しい地図
• 0からnの範囲のiについては、
  • v：=G [i]
  • vのサイズが1と同じ場合、
    • s：=v [0]
    • 訪問中に存在しない場合は、
      • visit [s]：=[i]
    • それ以外の場合、
      • 訪問の最後にiを追加します[s]
  • それ以外の場合、vのサイズが0と同じ場合、
    • n：=n-1
• tmp：=0
• 訪問中のkごとに、
  • x：=訪問のサイズ[k] -t
  • x> 0の場合、
    • tmp：=tmp + x
• return 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