पूरक ग्राफ
ग्राफ सिद्धांत के गणितीय क्षेत्र में, एक ग्राफ G का पूरक या व्युत्क्रम समान शीर्ष पर एक ग्राफ H होता है जैसे कि H दो भिन्न-भिन्न कोने सन्निकट होते हैं यद्यपि केवल G सन्निकट नहीं होते हैं .अर्थात्, एक ग्राफ़ के पूरक को एक संपूर्ण ग्राफ़ बनाने के लिए आवश्यक सभी लुप्त किनारों को भरता है, और उन सभी किनारों को हटा देता है जो पहले वहां थे।[1]
पूरक ग्राफ का पूरक सेट सिद्धांत नहीं होता है; केवल पूरक किनारे होते हैं।
परिभाषा
मान लिया G = (V, E) साधारण है और K में V. के सभी 2-तत्व उपसमुच्चय सम्मिलित होता है। तब H = (V, K \ E) का G पूरक है ,[2] जहाँ K \ E में E में K.का सापेक्ष पूरक होता है तथा निर्देशित रेखांकन के लिए, पूरक को उसी तरह से परिभाषित किया जा सकता है, जैसे कि एक ही शीर्ष सेट पर एक निर्देशित ग्राफ के रूप में, सभी 2-तत्वों के आदेशित जोड़े के सेट का उपयोग करके V सेट के स्थान पर K उपरोक्त सूत्र में उपयोग किया जाता हैं। ग्राफ के आसन्न मैट्रिक्स A के संदर्भ में, यदि Q एक ही संख्या के शीर्षों के पूर्ण ग्राफ के आसन्न मैट्रिक्स है, तो पूरक के आसन्न मैट्रिक्स Q-A.होता है।
मल्टीग्राफ के लिए पूरक को परिभाषित नहीं किया गया है। ग्राफ़ में जो स्व-लूप की अनुमति देता है वो 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.
