पूरक ग्राफ
ग्राफ सिद्धांत के गणितीय क्षेत्र में, एक ग्राफ का पूरक या व्युत्क्रम (असतत गणित) G एक ग्राफ है H एक ही शीर्ष (ग्राफ सिद्धांत) पर जैसे कि दो अलग-अलग कोने H सन्निकट हैं यदि और केवल यदि वे सन्निकट नहीं हैं G. अर्थात्, एक ग्राफ़ के पूरक को उत्पन्न करने के लिए, एक संपूर्ण ग्राफ़ बनाने के लिए आवश्यक सभी लापता किनारों (ग्राफ़ सिद्धांत) को भरता है, और उन सभी किनारों को हटा देता है जो पहले वहां थे।[1] पूरक ग्राफ का पूरक (सेट सिद्धांत) नहीं है; केवल किनारे पूरक हैं।
परिभाषा
होने देना G = (V, E) एक साधारण ग्राफ बनो और चलो K के सभी 2-तत्व सबसेट से मिलकर बनता है V. तब H = (V, K \ E) का पूरक है G,[2] कहाँ K \ E का सापेक्ष पूरक है E में K. निर्देशित रेखांकन के लिए, पूरक को उसी तरह से परिभाषित किया जा सकता है, जैसे कि एक ही शीर्ष सेट पर एक निर्देशित ग्राफ के रूप में, सभी 2-तत्वों के आदेशित जोड़े के सेट का उपयोग करके V सेट के स्थान पर K उपरोक्त सूत्र में। ग्राफ के आसन्न मैट्रिक्स ए के संदर्भ में, यदि क्यू एक ही संख्या के शीर्षों के पूर्ण ग्राफ के आसन्न मैट्रिक्स है (यानी सभी प्रविष्टियां एकता हैं जो विकर्ण प्रविष्टियों को छोड़कर शून्य हैं), तो पूरक के आसन्न मैट्रिक्स ए क्यूए है।
मल्टीग्राफ के लिए पूरक को परिभाषित नहीं किया गया है। ग्राफ़ में जो लूप (ग्राफ़ सिद्धांत) की अनुमति देता है | स्वयं-लूप (लेकिन एकाधिक आसन्न नहीं) के पूरक G को प्रत्येक वर्टेक्स में एक सेल्फ-लूप जोड़कर परिभाषित किया जा सकता है जिसमें एक नहीं है G, और अन्यथा उपरोक्त के समान सूत्र का उपयोग करना। हालांकि, यह ऑपरेशन साधारण ग्राफ़ के लिए एक से अलग है, क्योंकि इसे बिना किसी सेल्फ-लूप वाले ग्राफ़ पर लागू करने से सभी कोने पर सेल्फ़-लूप वाला ग्राफ़ बन जाएगा।
अनुप्रयोग और उदाहरण
पूरक के माध्यम से कई ग्राफ-सैद्धांतिक अवधारणाएं एक दूसरे से संबंधित हैं:
- एक किनारे रहित ग्राफ का पूरक एक पूर्ण ग्राफ है और इसके विपरीत।
- किसी ग्राफ़ के पूरक ग्राफ़ का कोई प्रेरित सबग्राफ़ G इसी प्रेरित सबग्राफ का पूरक है G.
- एक ग्राफ में एक स्वतंत्र सेट (ग्राफ सिद्धांत) पूरक ग्राफ में एक क्लिक (ग्राफ सिद्धांत) है और इसके विपरीत। यह पिछले दो गुणों का एक विशेष मामला है, क्योंकि एक स्वतंत्र सेट एक एजलेस प्रेरित सबग्राफ है और एक क्लिक एक पूर्ण प्रेरित सबग्राफ है।
- ग्राफ़ का ग्राफ ऑटोमोर्फिज्म समूह इसके पूरक का ऑटोमोर्फिज़्म समूह है।
- प्रत्येक त्रिभुज-मुक्त ग्राफ़ का पूरक एक पंजा-मुक्त ग्राफ़ है,[3] हालांकि उलटा सच नहीं है।
स्व-पूरक रेखांकन और ग्राफ वर्ग
एक स्व-पूरक ग्राफ एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के लिए ग्राफ समरूपता है।[1]उदाहरणों में चार-वर्टेक्स पथ ग्राफ़ और पाँच-वर्टेक्स चक्र ग्राफ़ शामिल हैं। स्व-पूरक रेखांकन का कोई ज्ञात लक्षण वर्णन नहीं है।
ग्राफ़ के कई वर्ग स्व-पूरक हैं, इस अर्थ में कि इनमें से किसी एक वर्ग में किसी भी ग्राफ़ का पूरक उसी वर्ग में एक और ग्राफ़ है।
- सही रेखांकन वे रेखांकन होते हैं, जिनमें प्रत्येक प्रेरित सबग्राफ के लिए, वर्णिक संख्या अधिकतम क्लिक के आकार के बराबर होती है। तथ्य यह है कि एक बिल्कुल सही ग्राफ का पूरक भी सही है, लेज़्लो लोवाज़ का सही ग्राफ प्रमेय है।[4]
- कोग्राफ को ऐसे ग्राफ़ के रूप में परिभाषित किया जाता है, जिन्हें अलग-अलग संघ और पूरक संचालन द्वारा एकल कोने से बनाया जा सकता है। वे रेखांकन के एक स्व-पूरक परिवार का निर्माण करते हैं: किसी भी कॉग्राफ का पूरक एक और अलग कॉग्राफ है। एक से अधिक वर्टेक्स के कोग्राफ के लिए, प्रत्येक पूरक जोड़ी में बिल्कुल एक ग्राफ जुड़ा हुआ है, और कॉग्राफ की एक समकक्ष परिभाषा यह है कि उनके प्रत्येक जुड़े प्रेरित सबग्राफ में एक डिस्कनेक्ट पूरक है। एक और, स्व-पूरक परिभाषा यह है कि वे चार-शिखर पथ के रूप में बिना किसी प्रेरित सबग्राफ वाले ग्राफ़ हैं।[5]
- रेखांकन का एक अन्य स्व-पूरक वर्ग विभाजन रेखांकन का वर्ग है, ऐसे रेखांकन जिनमें कोने को एक क्लिक और एक स्वतंत्र सेट में विभाजित किया जा सकता है। वही विभाजन पूरक ग्राफ में एक स्वतंत्र सेट और एक क्लिक देता है।[6]
- दहलीज ग्राफ वे ग्राफ़ होते हैं जो बार-बार या तो एक स्वतंत्र वर्टेक्स (बिना किसी पड़ोसी के) या एक सार्वभौमिक शिखर (पहले से जोड़े गए सभी शीर्षों के निकट) को जोड़कर बनाए जाते हैं। ये दो ऑपरेशन पूरक हैं और वे रेखांकन का एक स्व-पूरक वर्ग उत्पन्न करते हैं।[7]
एल्गोरिथम पहलू
ग्राफ़ पर एल्गोरिदम के विश्लेषण में, एक ग्राफ़ और उसके पूरक के बीच का अंतर एक महत्वपूर्ण है, क्योंकि एक विरल ग्राफ़ (जोड़े के जोड़े की संख्या की तुलना में किनारों की एक छोटी संख्या के साथ) में सामान्य रूप से विरल पूरक नहीं होगा , और इसलिए एक एल्गोरिथम जो किसी दिए गए ग्राफ़ पर किनारों की संख्या के अनुपात में समय लेता है, यदि उसी एल्गोरिथम को पूरक ग्राफ़ के स्पष्ट प्रतिनिधित्व पर चलाया जाता है, तो बहुत अधिक समय लग सकता है। इसलिए, शोधकर्ताओं ने एल्गोरिदम का अध्ययन किया है जो एक इनपुट ग्राफ के पूरक पर मानक ग्राफ संगणना करते हैं, एक निहित ग्राफ प्रतिनिधित्व का उपयोग करते हुए पूरक ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं होती है। विशेष रूप से, पूरक ग्राफ पर गहराई-पहली खोज या चौड़ाई-पहली खोज का अनुकरण करना संभव है, जो कि दिए गए ग्राफ के आकार में रैखिक है, भले ही पूरक ग्राफ का आकार बहुत बड़ा हो। .[8]पूरक ग्राफ की कनेक्टिविटी से संबंधित अन्य गुणों की गणना करने के लिए इन सिमुलेशन का उपयोग करना भी संभव है।[8][9]
संदर्भ
- ↑ 1.0 1.1 Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 6, ISBN 0-444-19451-7.
- ↑ Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.
- ↑ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs" (PDF), Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser., vol. 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738..
- ↑ Lovász, László (1972a), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4.
- ↑ Corneil, D. G.; Lerchs, H.; Stewart Burlingham, L. (1981), "Complement reducible graphs", Discrete Applied Mathematics, 3 (3): 163–174, doi:10.1016/0166-218X(81)90013-5, MR 0619603.
- ↑ Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, Theorem 6.1, p. 150, ISBN 0-12-289260-7, MR 0562306.
- ↑ Golumbic, Martin Charles; Jamison, Robert E. (2006), "Rank-tolerance graph classes", Journal of Graph Theory, 52 (4): 317–340, doi:10.1002/jgt.20163, MR 2242832.
- ↑ 8.0 8.1 Ito, Hiro; Yokoyama, Mitsuo (1998), "Linear time algorithms for graph search and connectivity determination on complement graphs", Information Processing Letters, 66 (4): 209–213, doi:10.1016/S0020-0190(98)00071-4, MR 1629714.
- ↑ Kao, Ming-Yang; Occhiogrosso, Neill; Teng, Shang-Hua (1999), "Simple and efficient graph compression schemes for dense and complement graphs", Journal of Combinatorial Optimization, 2 (4): 351–359, doi:10.1023/A:1009720402326, MR 1669307.
