주어진 무방향 그래프가 있다고 가정합니다. 크기가 l인 독립 집합이 포함되어 있는지 확인해야 합니다. 크기가 l인 독립적인 집합이 있으면 Yes를 반환하고 그렇지 않으면 No를 반환합니다.
그래프에서 독립 집합은 서로 직접 연결되지 않은 정점 집합으로 정의된다는 점을 명심해야 합니다.
따라서 입력이 L =4와 같으면
그러면 출력은 yes가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
is_valid() 함수를 정의합니다. 그래프가 필요합니다. ar
-
범위 0에서 arr 크기까지의 i에 대해 수행
-
범위 i + 1에서 arr 크기까지의 j에 대해 수행
-
그래프[arr[i], arr[j]]가 1과 같으면
-
거짓을 반환
-
-
-
-
참을 반환
-
solve() 함수를 정의합니다. 그래프, arr, k, index, sol이 필요합니다.
-
k가 0과 같으면
-
is_valid(graph, arr)가 True와 같으면
-
솔[0] :=참
-
반환
-
-
그렇지 않으면
-
인덱스>=k인 경우
-
return(solve(graph, arr[인덱스 0에서 끝까지] [인덱스], k-1, 인덱스-1, sol) 또는 solve(graph, arr[인덱스 0에서 끝까지], k, 인덱스- 1, 솔))
-
-
그렇지 않으면
-
return solve(graph, arr[인덱스 0에서 끝까지] 목록을 [인덱스], k-1, 인덱스-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