สมมติว่าเรามีกราฟที่ไม่ได้บอกทิศทาง เราต้องตรวจสอบว่ามีชุดขนาด l อิสระหรือไม่ หากมีชุดขนาดอิสระใด ๆ ให้ส่งคืนใช่มิฉะนั้นไม่ใช่
เราต้องจำไว้ว่าชุดอิสระในกราฟถูกกำหนดให้เป็นชุดของจุดยอดซึ่งไม่ได้เชื่อมต่อกันโดยตรง
ดังนั้น หากอินพุตเป็น L =4
แล้วผลลัพธ์จะเป็นใช่
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน is_valid() นี่จะเป็นกราฟ arr
-
สำหรับฉันในช่วง 0 ถึงขนาดของ arr ทำ
-
สำหรับ j ในช่วง i + 1 ถึงขนาดของ arr ทำ
-
ถ้า graph[arr[i], arr[j]] เหมือนกับ 1 แล้ว
-
คืนค่าเท็จ
-
-
-
-
คืนค่า True
-
กำหนดฟังก์ชัน Solve() จะได้กราฟ arr k ดัชนี โซล
-
ถ้า k เท่ากับ 0 แล้ว
-
ถ้า is_valid(graph, arr) เหมือนกับ True แล้ว
-
sol[0] :=จริง
-
กลับ
-
-
มิฉะนั้น
-
ถ้าดัชนี>=k แล้ว
-
return(แก้(กราฟ, arr[จากดัชนี 0 ถึงสิ้นสุด] เชื่อมรายการด้วย [ดัชนี], k-1, ดัชนี-1, โซล) หรือแก้(กราฟ, arr[จากดัชนี 0 ถึงจุดสิ้นสุด], k, ดัชนี- 1 โซล))
-
-
มิฉะนั้น
-
return Solve(กราฟ, arr[จากดัชนี 0 ถึงปลาย] เชื่อมรายการด้วย [ดัชนี], k-1, ดัชนี-1, โซล)
-
-
-
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
