पायथन में ग्राफ में सबसे बड़े क्लिक का न्यूनतम आकार ज्ञात करने का प्रोग्राम

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

इसलिए, यदि इनपुट है nodes = 4, edges = 4; तो आउटपुट 2 होगा।

उपरोक्त ग्राफ में, क्लिक का अधिकतम आकार 2 है।

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

एक फ़ंक्शन helper() परिभाषित करें। यह x, y लेगा
- ga := x mod y
- gb := y - ga
- sa := (x / y) का भागफल + 1
- sb := (x / y) का भागफल
- ga * gb * sa * sb + ga *(ga - 1) * sa * sa / 2 + gb * (gb - 1) * sb * sb / 2 वापस करें
i := 1
j := nodes + 1
जब तक i + 1 < j, करें
- p := i + floor((j - i) / 2)
- k := helper(nodes, p)
- यदि k < edges, तो
  - i := p
- अन्यथा,
  - j := p
j वापस करें

उदाहरण

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

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