डीएए - मैक्स क्लिक्स

एक अप्रत्यक्ष ग्राफ में, ए cliqueदिए गए ग्राफ का पूरा उप-ग्राफ है। पूर्ण उप-ग्राफ़ का अर्थ है, इस उप-ग्राफ़ के सभी कोने इस उप-ग्राफ़ के अन्य सभी कोने से जुड़े हुए हैं।

मैक्स-क्लिक समस्या ग्राफ के अधिकतम क्लिक को खोजने की कम्प्यूटेशनल समस्या है। मैक्स क्लिक का उपयोग कई वास्तविक दुनिया की समस्याओं में किया जाता है।

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

एक अधिकतम क्लिक को खोजने के लिए, कोई भी व्यवस्थित रूप से सभी सबसेट का निरीक्षण कर सकता है, लेकिन कुछ दर्जन से अधिक वर्टीकल वाले नेटवर्कों के लिए इस तरह की ब्रूट-फोर्स खोज बहुत समय लेने वाली है।

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

विश्लेषण

मैक्स-क्लिक समस्या एक गैर-नियतात्मक एल्गोरिथ्म है। इस एल्गोरिथ्म में, पहले हम एक सेट को निर्धारित करने का प्रयास करते हैंk अलग-अलग कोने और फिर हम यह जांचने की कोशिश करते हैं कि क्या ये कोने एक पूरा ग्राफ बनाते हैं।

इस समस्या को हल करने के लिए कोई बहुपद समय नियतात्मक एल्गोरिथ्म नहीं है। यह समस्या एनपी-पूर्ण है।

उदाहरण

निम्नलिखित ग्राफ पर एक नज़र डालें। यहां, उप-ग्राफ जिसमें कोने 2, 3, 4 और 6 हैं, एक पूरा ग्राफ बनाता है। इसलिए, यह उप-ग्राफ एक हैclique। चूंकि यह प्रदान किए गए ग्राफ का अधिकतम पूर्ण उप-ग्राफ है, यह ए है4-Clique