मान लीजिए कि हमारे पास एक अप्रत्यक्ष ग्राफ दिया गया है; हमें यह जांचना है कि इसमें आकार का एक स्वतंत्र सेट है या नहीं। यदि आकार l का कोई स्वतंत्र सेट है तो हाँ लौटाएँ अन्यथा नहीं।
हमें यह ध्यान रखना होगा कि ग्राफ़ में एक स्वतंत्र समुच्चय को ऐसे शीर्षों के समुच्चय के रूप में परिभाषित किया जाता है जो एक दूसरे से सीधे नहीं जुड़े होते हैं।
इसलिए, यदि इनपुट L =4 जैसा है,
तो आउटपुट हाँ होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन को परिभाषित करें is_valid() । यह ग्राफ लेगा, गिरफ्तार करें
-
मेरे लिए 0 से लेकर गिरफ्तारी के आकार तक, करें
-
j के लिए i + 1 से arr के आकार की श्रेणी में, करें
-
अगर ग्राफ़[arr[i], arr[j]] 1 के समान है, तो
-
झूठी वापसी
-
-
-
-
सही लौटें
-
फ़ंक्शन को हल करें () परिभाषित करें। यह ग्राफ, एआर, के, इंडेक्स, सोल लेगा
-
यदि k, 0 के समान है, तो
-
अगर is_valid(graph, arr) सच के समान है, तो
-
सोल [0] :=सच
-
वापसी
-
-
अन्यथा,
-
यदि अनुक्रमणिका>=k, तो
-
वापसी (समाधान (ग्राफ, एआर [इंडेक्स 0 से अंत तक] एक सूची को [इंडेक्स], के -1, इंडेक्स -1, सोल) के साथ संयोजित करें या हल करें (ग्राफ, एआर [इंडेक्स 0 से अंत तक], के, इंडेक्स- 1, सोल))
-
-
अन्यथा,
-
रिटर्न सॉल्व (ग्राफ, एआर [इंडेक्स 0 से अंत तक] एक सूची को [इंडेक्स], के -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