क्लिक (ग्राफ सिद्धांत)

• 23 × 1-वर्टेक्स क्लिक्स (शीर्ष)
• 42 × 2-वर्टेक्स क्लिक्स (किनारे)
• 19 × 3-वर्टेक्स क्लिक्स (हल्का और गहरा नीला त्रिकोण), और
• 2 × 4-वर्टेक्स क्लिक्स (गहरा नीला क्षेत्र)।

के साथ ग्राफ। 11 हल्के नीले त्रिकोण अधिकतम समूह बनाते हैं। दो गहरे नीले 4-क्लिक अधिकतम और उच्चतम दोनों हैं, और ग्राफ की क्लिक संख्या 4 है।

ग्राफ सिद्धांत के गणित क्षेत्र में, क्लिक (/ˈkliːk/ या /ˈklɪk/) अप्रत्यक्ष ग्राफ़ के शीर्षों का एक उपसमूह है, जैसे कि क्लिक में प्रत्येक दो अलग-अलग शिखर आसन्न (ग्राफ़ सिद्धांत) हैं। यानी ग्राफ का एक समूह $G$ का प्रेरित सबग्राफ है $G$ वह पूरा ग्राफ है। क्लिक्स ग्राफ़ सिद्धांत की मूल अवधारणाओं में से एक हैं और ग्राफ़ पर कई अन्य गणितीय समस्याओं और निर्माणों में उपयोग किए जाते हैं। कंप्यूटर विज्ञान में क्लिक्स का भी अध्ययन किया गया है: यह पता लगाने का कार्य कि क्या एक ग्राफ़ (असतत गणित) (क्लिक समस्या) में दिए गए आकार का एक समूह है, एन.पी-पूर्ण है, लेकिन इस कठोरता के परिणाम के बावजूद, क्लिक्स खोजने के लिए कई कलन विधि अध्ययन किया गया है।

यद्यपि पूर्ण ग्राफ का अध्ययन कम से कम रैमसे सिद्धांत के ग्राफ-सैद्धांतिक सुधार के लिए वापस चला जाता है Erdős & Szekeres (1935), क्लिक शब्द से आया है Luce & Perry (1949), जिन्होंने लोगों के मॉडल समूहों के लिए सामाजिक नेटवर्क में पूर्ण सबग्राफ का उपयोग किया; यानी ऐसे लोगों का समूह जिनमें सभी एक-दूसरे को जानते हों। विज्ञान और विशेष रूप से जैव सूचना विज्ञान मे क्लिक्स के कई अन्य अनुप्रयोग हैं।

परिभाषाएँ

एक क्लिक, C, एक अप्रत्यक्ष ग्राफ में G = (V, E) शीर्ष (ग्राफ सिद्धांत) का एक सबसमुच्चय है, C ⊆ V, जैसे कि हर दो अलग-अलग कोने आसन्न हैं। यह इस शर्त के बराबर है कि प्रेरित सबग्राफ G प्रेरक C एक पूरा ग्राफ है। कुछ मामलों में, क्लिक शब्द सीधे सबग्राफ को भी संदर्भित कर सकता है।

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

एक ग्राफ का अधिकतम क्लिक, G, एक क्लिक है, जैसे कि अधिक शीर्षों वाला क्लिक नहीं है। इसके अलावा, क्लिक संख्या ω(G) ग्राफ का G अधिकतम क्लिक में शीर्षों की संख्या है G.

प्रतिच्छेदन संख्या (ग्राफ सिद्धांत)। G क्लिक्स की सबसे छोटी संख्या है जो एक साथ सभी किनारों को कवर करते हैं G.

एक ग्राफ की क्लिक कवर संख्या G के क्लिक्स की सबसे छोटी संख्या है G जिसका संघ वर्टिकल के समुच्चय को कवर करता है V ग्राफ का।

किसी ग्राफ़ का अधिकतम क्लिक ट्रांसवर्सल गुण के साथ वर्टिकल का एक सबसमुच्चय होता है, जिसमें ग्राफ़ के प्रत्येक अधिकतम क्लिक में सबसमुच्चय में कम से कम एक वर्टेक्स होता है।

एक क्लिक के विपरीत एक स्वतंत्र समुच्चय (ग्राफ सिद्धांत) है, इस अर्थ में कि प्रत्येक क्लिक पूरक ग्राफ में एक स्वतंत्र समुच्चय से मेल खाता है। कवर पर क्लिक करें समस्या का संबंध यथासंभव कुछ क्लिकों को खोजने से है, जिसमें ग्राफ़ में प्रत्येक शीर्ष शामिल है।

एक संबंधित अवधारणा एक द्विदलीय, एक पूर्ण द्विदलीय ग्राफ है। ग्राफ़ के द्विदलीय आयाम, ग्राफ़ के सभी किनारों को कवर करने के लिए आवश्यक बाइक्लिक की न्यूनतम संख्या है।

गणित

क्लिक्स से संबंधित गणितीय परिणामों में निम्नलिखित शामिल हैं।

• तुरान की प्रमेय घने ग्राफ़ में एक क्लिक के आकार पर एक निचली सीमा देती है। यदि किसी ग्राफ़ में पर्याप्त रूप से कई किनारे हैं, तो इसमें एक बड़ा समूह होना चाहिए। उदाहरण के लिए, प्रत्येक ग्राफ के साथ $n$ शिखर और अधिक $\scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil$ किनारों में तीन-शीर्ष समूह होना चाहिए।
• रैमसे के प्रमेय में कहा गया है कि प्रत्येक ग्राफ़ या इसके पूरक ग्राफ़ में कम से कम लघुगणकीय संख्याओं के साथ एक क्लिक होता है।
• परिणाम के अनुसार Moon & Moser (1965), 3n शीर्षों वाले ग्राफ़ में अधिकतम 3 हो सकते हैंⁿ अधिकतम क्लिक्स। इस सीमा को पूरा करने वाले रेखांकन चंद्रमा-मोजर रेखांकन K हैं_3,3,..., तुरान के प्रमेय में चरम मामलों के रूप में उत्पन्न होने वाले लाइन ग्राफ का एक विशेष मामला।
• हैडविगर अनुमान (ग्राफ थ्योरी) | हैडविगर का अनुमान, अभी भी अप्रमाणित है, एक ग्राफ (इसकी हैडविगर संख्या) में सबसे बड़े क्लिक ग्राफ माइनर के आकार को इसकी रंगीन संख्या से संबंधित करता है।
• एर्डोस-फैबर-लोवाज़ अनुमान एक अन्य अप्रमाणित कथन है जो ग्राफ रंग को क्लिक्स से संबंधित करता है।

रेखांकन के कई महत्वपूर्ण वर्गों को उनके क्लिक्स द्वारा परिभाषित या वर्णित किया जा सकता है:

• एक क्लस्टर ग्राफ एक ऐसा ग्राफ है जिसका जुड़ा हुआ घटक (ग्राफ सिद्धांत) क्लिक्स हैं।
• एक ब्लॉक ग्राफ एक ऐसा ग्राफ है जिसके द्विसंबद्ध घटक क्लिक होते हैं।
• एक कॉर्डल ग्राफ एक ऐसा ग्राफ है जिसके शीर्षों को एक पूर्ण उन्मूलन क्रम में क्रमबद्ध किया जा सकता है, एक ऐसा क्रम जिससे कि प्रत्येक शीर्ष v का पड़ोस (ग्राफ सिद्धांत) जो v की तुलना में बाद में क्रम में आता है।
• एक कोग्राफ एक ऐसा ग्राफ है जिसके सभी प्रेरित सबग्राफ में यह संपत्ति होती है कि कोई भी अधिकतम समूह किसी एकल शीर्ष में किसी भी अधिकतम स्वतंत्र समुच्चय को काटता है।
• एक अंतराल ग्राफ एक ऐसा ग्राफ है जिसकी अधिकतम क्लिक्स को इस तरह से ऑर्डर किया जा सकता है कि, प्रत्येक वर्टेक्स v के लिए, v वाले क्लिक्स क्रम में लगातार होते हैं।
• एक रेखा ग्राफ एक ऐसा ग्राफ है जिसके किनारों को किनारे-असंबद्ध क्लिक्स द्वारा इस तरह से कवर किया जा सकता है कि प्रत्येक वर्टेक्स कवर में ठीक दो क्लिक्स से संबंधित हो।
• एक आदर्श ग्राफ एक ऐसा ग्राफ है जिसमें क्लिक संख्या प्रत्येक प्रेरित सबग्राफ में रंगीन संख्या के बराबर होती है।
• एक विभाजित ग्राफ एक ऐसा ग्राफ है जिसमें कुछ समूह में प्रत्येक किनारे का कम से कम एक समापन बिंदु होता है।
• त्रिभुज-मुक्त ग्राफ़ एक ऐसा ग्राफ़ होता है, जिसमें इसके शीर्ष और किनारों के अलावा कोई अन्य समूह नहीं होता है।

इसके अतिरिक्त, कई अन्य गणितीय निर्माणों में ग्राफ़ में क्लिक शामिल हैं। उनमें से,

• ग्राफ G का क्लिक कॉम्प्लेक्स एक सार सरल जटिल X(G) है जिसमें G में हर क्लिक के लिए एक सिम्प्लेक्स है
• एक सिंप्लेक्स ग्राफ एक अप्रत्यक्ष ग्राफ κ(G) है जिसमें ग्राफ G में प्रत्येक क्लिक के लिए एक वर्टेक्स होता है और एक किनारा जो दो क्लिक्स को जोड़ता है जो एक शीर्ष से भिन्न होता है। यह माध्यिका ग्राफ का एक उदाहरण है, और एक ग्राफ के समूहों पर माध्य बीजगणित के साथ जुड़ा हुआ है: तीन समूहों ए, बी, और सी का औसत एम (ए, बी, सी) वह चक्कर है जिसका शिखर कम से कम दो क्लिक ए, बी और सी।
• मैं एक क्लिक हूँ दो ग्राफ़ को एक साझा क्लिक के साथ मर्ज करके संयोजित करने की एक विधि है।
• क्लिक-चौड़ाई एक ग्राफ़ की जटिलता की एक धारणा है, जो अलग-अलग वर्टेक्स लेबल की न्यूनतम संख्या के संदर्भ में अलग-अलग यूनियनों, रीलेबलिंग ऑपरेशंस और ऑपरेशंस से ग्राफ़ बनाने के लिए आवश्यक है, जो दिए गए लेबल के साथ कोने के सभी जोड़े को जोड़ते हैं। क्लिक-चौड़ाई वाले ग्राफ़ वास्तव में क्लिक्स के अलग-अलग यूनियन हैं।
• किसी ग्राफ़ का चौराहा ग्राफ (ग्राफ़ थ्योरी) ग्राफ़ के सभी किनारों को कवर करने के लिए आवश्यक क्लिक्स की न्यूनतम संख्या है।
• किसी ग्राफ का ग्राफ क्लिक करें उसके अधिकतम क्लिक्स का प्रतिच्छेदन ग्राफ है।

उप-अनुच्छेदों को पूरा करने के लिए बारीकी से संबंधित अवधारणाएँ पूर्ण रेखांकन के उपखंड (ग्राफ सिद्धांत) हैं और पूर्ण ग्राफ नाबालिग हैं। विशेष रूप से, कुराटोव्स्की के प्रमेय और वैगनर के प्रमेय क्रमशः वर्जित पूर्ण और पूर्ण द्विदलीय ग्राफ उपखंडों और नाबालिगों द्वारा प्लेनर ग्राफ ़ की विशेषता बताते हैं।

कंप्यूटर विज्ञान

कम्प्यूटर साइंस में, क्लिक समस्या दिए गए ग्राफ में अधिकतम क्लिक, या सभी क्लिकों को खोजने की संगणनात्मक समस्या है। यह एन.पी-पूर्ण है, कार्प की 21 एन.पी-पूर्ण समस्याओं में से एक है। निश्चित-मापदण्ड प्रचण्ड़, अनुमानित करना कठिन है। फिर भी, कंप्यूटिंग क्लिक्स के लिए कई कलन विधि विकसित किए गए हैं, या तो घातीय समय (जैसे ब्रॉन-केरबोश कलन विधि ) में चल रहे हैं या ग्राफ़ परिवारों जैसे प्लानर ग्राफ़ या सही ग्राफ़ के लिए विशेष हैं, जिसके लिए समस्या को बहुपद समय में हल किया जा सकता है।

अनुप्रयोग

"क्लिक" शब्द, अपने ग्राफ-सैद्धांतिक उपयोग में, लूस & पेरी (1949) के कार्य से उत्पन्न हुआ, जिन्होंने सामाजिक नेटवर्क में मॉडल क्लिक्स (उन लोगों के समूह जो सभी एक दूसरे को जानते हैं) के लिए पूर्ण सबग्राफ का उपयोग किया। फेसटिनजर (1949) द्वारा कम प्रौद्योगिकी शब्दों का उपयोग करते हुए एक लेख में इसी परिभाषा का उपयोग किया गया था। दोनों कार्य आव्यूह का उपयोग करके सामाजिक नेटवर्क में क्लिक्स को उजागर करने से संबंधित हैं। सामाजिक समूहों को सैद्धांतिक रूप से मॉडल करने के निरंतर प्रयासों के लिए, अल्बा (1973), पीय (1974), और डोरियन & वुडार्ड (1994) का उदाहरण देखें।

जैव सूचना विज्ञान से कई अलग-अलग समस्याओं को क्लिक्स का उपयोग करके प्रतिरूपित किया गया है। उदाहरण के लिए, बेन-डोर, शमीर & यखिनी (1999) गुच्छन पित्रैक अभिव्यंजना डेटा की समस्या को एक ऐसे ग्राफ़ में बदलने के लिए आवश्यक परिवर्तनों की न्यूनतम संख्या खोजने में से एक के रूप में मॉडल करें, जो डेटा को क्लिक्स के असंयुक्त संघ के रूप में बनाए गए ग्राफ़ में बदल देता है; तनय, शरण & शमीर (2002) अभिव्यक्ति डेटा के लिए इसी तरह की एक समान द्विगुणित समस्या पर चर्चा करते हैं जिसमें समूहों को क्लिक्स की आवश्यकता होती है। सुगिहारा (1984) खाद्य श्रृंखला में पारिस्थितिक आलों को मॉडल करने के लिए क्लिक्स का उपयोग करता है। डे & सैंकॉफ़ (1986) ने विकासवादी पेड़ों का उल्लेख करने की समस्या का वर्णन एक ग्राफ में अधिकतम क्लिकों को खोजने में किया है, जिसमें प्रजातियों की अपनी कोने की विशेषताएं हैं, जहाँ दो कोने एक किनारे को साझा करते हैं यदि वहाँ उन दो वर्णों के संयोजन के लिए एक पूर्ण जातिवृत्त उपस्थित है। समुद्राला & मोल्ट (1998) मॉडल प्रोटीन संरचना की भविष्यवाणी ग्राफ में क्लिक्स खोजने की समस्या के रूप में जिसके कोने प्रोटीन के उपइकाइयों की स्थिति का प्रतिनिधित्व करता है और प्रोटीन-प्रोटीन पारस्परिक प्रभाव नेटवर्क में क्लिक्स की खोज करके, स्पिरिन & मिर्नी (2003) ने प्रोटीन के समूह पाए गए जो एक-दूसरे के साथ निकटता से परस्पर प्रभाव करते हैं और समूह के बाहर प्रोटीन पर परस्पर प्रभाव करते हैं। पावर ग्राफ विश्लेषण इन नेटवर्कों में क्लिक्स और संबंधित संरचनाओं को ढूंढकर जटिल जैविक नेटवर्क को सरल बनाने की विधि है।

विद्युत अभियन्त्रण में, प्रिहार (1956) संचार नेटवर्क का विश्लेषण करने के लिए क्लिक्स का उपयोग करता है, और पॉल & अनगर (1959) आंशिक रूप से निर्दिष्ट बूलियन कार्यों की गणना के लिए कुशल विद्युत परिपथ डिजाइन करने के लिए उनका उपयोग करते है। स्वत: परीक्षण पैटर्न उत्पादन में क्लिक्स का भी उपयोग किया गया है: संभावित दोषों के असंगतता ग्राफ में एक बड़ा समूह परीक्षण समुच्चय के आकार पर कम सीमा प्रदान करता है। कांग & स्मिथ (1993) छोटे सबयूनिट में इलेक्ट्रॉनिक परिपथ के पदानुक्रमित विभाजन को खोजने में क्लिक्स के उपयोग का वर्णन करता है।

रसायन शास्त्र में, रोड्स et al. (2003) किसी रासायनिक डेटाबेस में रसायनों का वर्णन करने के लिए क्लिक्स का उपयोग करें जिनमें लक्ष्य संरचना के साथ उच्च स्तर की समानता हो। कुहल, क्रिप्पेन & फ्रेज़ेन (1983) उन स्थितियों को मॉडल करने के लिए क्लिक्स का उपयोग करें जिनमें दो रसायन एक दूसरे से बंधेंगे।

यह भी देखें

• खेल क्लिक करें

संदर्भ

• Alba, Richard D. (1973), "A graph-theoretic definition of a sociometric clique" (PDF), Journal of Mathematical Sociology, 3 (1): 113–126, doi:10.1080/0022250X.1973.9989826, archived (PDF) from the original on 2011-05-03, retrieved 2009-12-14.
• Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", Journal of Classification, 3 (2): 187–224, doi:10.1007/BF01894188, S2CID 6092438.
• Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999), "Clustering gene expression patterns.", Journal of Computational Biology, 6 (3–4): 281–297, CiteSeerX 10.1.1.34.5341, doi:10.1089/106652799318274, PMID 10582567.
• Chang, Maw-Shang; Kloks, Ton; Lee, Chuan-Min (2001), "Maximum clique transversals", Graph-theoretic concepts in computer science (Boltenhagen, 2001), Lecture Notes in Comput. Sci., vol. 2204, Springer, Berlin, pp. 32–43, doi:10.1007/3-540-45477-2_5, ISBN 978-3-540-42707-0, MR 1905299.
• Cong, J.; Smith, M. (1993), "A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design", Proc. 30th International Design Automation Conference, pp. 755–760, CiteSeerX 10.1.1.32.735, doi:10.1145/157485.165119, ISBN 978-0897915779, S2CID 525253.
• Day, William H. E.; Sankoff, David (1986), "Computational complexity of inferring phylogenies by compatibility", Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432.
• Doreian, Patrick; Woodard, Katherine L. (1994), "Defining and locating cores and boundaries of social networks", Social Networks, 16 (4): 267–293, doi:10.1016/0378-8733(94)90013-2.
• Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry" (PDF), Compositio Mathematica, 2: 463–470, archived (PDF) from the original on 2020-05-22, retrieved 2009-12-19.
• Festinger, Leon (1949), "The analysis of sociograms using matrix algebra", Human Relations, 2 (2): 153–158, doi:10.1177/001872674900200205, S2CID 143609308.
• Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory, New York: John Wiley and Sons, ISBN 978-0-471-50046-9.
• Hamzaoglu, I.; Patel, J. H. (1998), "Test set compaction algorithms for combinational circuits", Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615, ISBN 978-1581130089, S2CID 12258606.
• Karp, Richard M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thatcher, J. W. (eds.), Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, archived from the original (PDF) on 2011-06-29, retrieved 2009-12-13.
• Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), "A combinatorial algorithm for calculating ligand binding", Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105, S2CID 122923018.
• Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en Topologie" (PDF), Fundamenta Mathematicae (in français), 15: 271–283, doi:10.4064/fm-15-1-271-283, archived (PDF) from the original on 2018-07-23, retrieved 2009-12-19.
• Luce, R. Duncan; Perry, Albert D. (1949), "A method of matrix analysis of group structure", Psychometrika, 14 (2): 95–116, doi:10.1007/BF02289146, hdl:10.1007/BF02289146, PMID 18152948, S2CID 16186758.
• Moon, J. W.; Moser, L. (1965), "On cliques in graphs", Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577.
• Paull, M. C.; Unger, S. H. (1959), "Minimizing the number of states in incompletely specified sequential switching functions", IRE Transactions on Electronic Computers, EC-8 (3): 356–367, doi:10.1109/TEC.1959.5222697.
• Peay, Edmund R. (1974), "Hierarchical clique structures", Sociometry, 37 (1): 54–65, doi:10.2307/2786466, JSTOR 2786466.
• Prihar, Z. (1956), "Topological properties of telecommunications networks", Proceedings of the IRE, 44 (7): 927–933, doi:10.1109/JRPROC.1956.275149, S2CID 51654879.
• Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), "CLIP: similarity searching of 3D databases using clique detection", Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507.
• Samudrala, Ram; Moult, John (1998), "A graph-theoretic algorithm for comparative modeling of protein structure", Journal of Molecular Biology, 279 (1): 287–302, CiteSeerX 10.1.1.64.8918, doi:10.1006/jmbi.1998.1689, PMID 9636717.
• Spirin, Victor; Mirny, Leonid A. (2003), "Protein complexes and functional modules in molecular networks", Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, doi:10.1073/pnas.2032324100, PMC 218723, PMID 14517352.
• Sugihara, George (1984), "Graph theory, homology and food webs", in Levin, Simon A. (ed.), Population Biology, Proc. Symp. Appl. Math., vol. 30, pp. 83–101.
• Tanay, Amos; Sharan, Roded; Shamir, Ron (2002), "Discovering statistically significant biclusters in gene expression data", Bioinformatics, 18 (Suppl. 1): S136–S144, doi:10.1093/bioinformatics/18.suppl_1.S136, PMID 12169541.
• Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in magyar), 48: 436–452

बाहरी संबंध

• Weisstein, Eric W., "Clique", MathWorld
• Weisstein, Eric W., "Clique Number", MathWorld