無向グラフにPythonで指定されたサイズの独立集合が含まれているかどうかを確認します

与えられた無向グラフがあるとしましょう。サイズlの独立集合が含まれているかどうかを確認する必要があります。サイズlの独立したセットがある場合は、「はい」を返します。それ以外の場合は「いいえ」を返します。

グラフ内の独立集合は、互いに直接接続されていない頂点の集合として定義されていることに注意する必要があります。

したがって、入力がL =4のような場合、

その場合、出力はyesになります

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

• 関数is_valid（）を定義します。これはグラフを取ります、arr

• 0からarrのサイズまでの範囲のiの場合、実行します

  • i + 1からarrのサイズまでの範囲のjについては、次のようにします

    • グラフ[arr[i]、arr [j]]が1と同じ場合、

      • Falseを返す

• Trueを返す

• 関数solve（）を定義します。これは、グラフ、arr、k、index、solを取ります

• kが0と同じ場合、

  • is_valid（graph、arr）がTrueと同じ場合、

    • sol [0]：=True

    • 戻る

  • それ以外の場合

    • インデックス>=kの場合、

      • return（solve（graph、arr [from index 0 to end]は、リストを[index]、k-1、index-1、sol）またはsolve（graph、arr [from index 0 to end]、k、index-と連結します。 1、sol））

    • それ以外の場合

      • return resolve（graph、arr [from index 0 to end]は、リストを[index]、k-1、index-1、sol）と連結します

例

理解を深めるために、次の実装を見てみましょう-

def is_valid(graph, arr):
   for i in range(len(arr)):
      for j in range(i + 1, len(arr)):
         if graph[arr[i]][arr[j]] == 1:
            return False
   return True
def solve(graph, arr, k, index, sol):
   if k == 0:
      if is_valid(graph, arr) == True:
         sol[0] = True
         return
      else:
         if index >= k:
            return (solve(graph, arr[:] + [index], k-1, index-1, sol) or solve(graph, arr[:], k, index-1, sol))
         else:
            return solve(graph, arr[:] + [index], k-1, index-1, sol)

graph = [
   [1, 1, 0, 0, 0],
   [1, 1, 1, 1, 1],
   [0, 1, 1, 0, 0],
   [0, 1, 0, 1, 0],
   [0, 1, 0, 0, 1]]
k = 4
arr = []
sol = [False]
solve(graph, arr[:], k, len(graph)-1, sol)
if sol[0]:
   print("Yes")
else:
   print("No")

入力

[[1, 1, 0, 0, 0],
[1, 1, 1, 1, 1],
[0, 1, 1, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 1]],
4

出力

Yes