ग्राफ़ में सबसे बड़े गुट के न्यूनतम आकार का पता लगाने का कार्यक्रम (पायथन)

मान लीजिए कि हमें एक ग्राफ दिया गया है और ग्राफ में सबसे बड़े समूह का न्यूनतम आकार ज्ञात करने के लिए कहा गया है। ग्राफ़ का एक समूह एक ग्राफ़ का एक उपसमुच्चय होता है, जहाँ प्रत्येक शीर्ष जोड़े आसन्न होते हैं, अर्थात प्रत्येक जोड़े के बीच एक किनारा मौजूद होता है। एक ग्राफ में सबसे बड़ा गुट ढूँढना बहुपद समय में संभव नहीं है, इसलिए एक छोटे ग्राफ के नोड्स और किनारों की संख्या को देखते हुए हमें इसमें सबसे बड़ा समूह खोजना होगा।

इसलिए, यदि इनपुट नोड्स =4, किनारों =4 की तरह है; तो आउटपुट 2 होगा।

ऊपर दिए गए ग्राफ़ में, एक गुट का अधिकतम आकार 2 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फंक्शन हेल्पर () को परिभाषित करें। इसमें x, y
  . लगेगा
  • ga :=x mod y
  • gb :=y - ga
  • sa :=के मान का भागफल(x / y) + 1
  • sb :=(x / y) के मान का भागफल
  • रिटर्न गा * gb * sa * sb + ga *(ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2
• मैं :=1
• j :=नोड्स + 1
• जबकि मैं + 1 <जे, करते हैं
  • p :=i + फ्लोर वैल्यू ((j - i) / 2)
  • k :=सहायक (नोड्स, p)
  • यदि k <किनारे हैं, तो
    • i :=p
  • अन्यथा,
    • j :=p
• रिटर्न जे

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

import math
def helper(x, y):
    ga = x % y
    gb = y - ga
    sa = x // y + 1
    sb = x // y
    return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def solve(nodes, edges):
    i = 1
    j = nodes + 1
    while i + 1 < j:
        p = i + (j - i) // 2
        k = helper(nodes, p)
        if k < edges:
            i = p
        else:
            j = p
    return j

print(solve(4, 4))

इनपुट

4,4

आउटपुट

2