पूरक ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Graph with same nodes but opposite connections as another}} thumb|upright=1.35|[[पीटरसन ग्राफ...")
 
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{short description|Graph with same nodes but opposite connections as another}}
{{short description|Graph with same nodes but opposite connections as another}}
[[File:Petersen graph complement.svg|thumb|upright=1.35|[[पीटरसन ग्राफ]] (बाईं ओर) और इसका पूरक ग्राफ (दाईं ओर)।]][[ग्राफ सिद्धांत]] के [[गणितीय]] क्षेत्र में, एक ग्राफ का पूरक या व्युत्क्रम (असतत गणित) {{mvar|G}} एक ग्राफ है {{mvar|H}} एक ही [[ शीर्ष (ग्राफ सिद्धांत) ]] पर जैसे कि दो अलग-अलग कोने {{mvar|H}} सन्निकट हैं यदि और केवल यदि वे सन्निकट नहीं हैं {{mvar|G}}. अर्थात्, एक ग्राफ़ के पूरक को उत्पन्न करने के लिए, एक संपूर्ण ग्राफ़ बनाने के लिए आवश्यक सभी लापता किनारों (ग्राफ़ सिद्धांत) को भरता है, और उन सभी किनारों को हटा देता है जो पहले वहां थे।<ref name="bm">{{citation
[[File:Petersen graph complement.svg|thumb|upright=1.35|[[पीटरसन ग्राफ]] बाईं ओर और इसका पूरक ग्राफ दाईं ओर होता हैं।]][[ग्राफ सिद्धांत]] के [[गणितीय]] क्षेत्र में, एक ग्राफ {{mvar|G}} का पूरक या व्युत्क्रम समान [[ शीर्ष (ग्राफ सिद्धांत) |शीर्ष]] पर एक ग्राफ {{mvar|H}} होता है जैसे कि {{mvar|H}} दो भिन्न-भिन्न कोने सन्निकट होते हैं यद्यपि  केवल {{mvar|G}} सन्निकट नहीं होते हैं .अर्थात्, एक ग्राफ़ के पूरक को एक संपूर्ण ग्राफ़ बनाने के लिए आवश्यक सभी लुप्त किनारों को भरता है, और उन सभी किनारों को हटा देता है जो पहले वहां थे।<ref name="bm">{{citation
  | last1=Bondy
  | last1=Bondy
  | first1=John Adrian
  | first1=John Adrian
Line 13: Line 13:
  | url=https://archive.org/details/graphtheorywitha0000bond/page/6
  | url=https://archive.org/details/graphtheorywitha0000bond/page/6
  | page=[https://archive.org/details/graphtheorywitha0000bond/page/6 6]
  | page=[https://archive.org/details/graphtheorywitha0000bond/page/6 6]
  }}.</ref> पूरक ग्राफ का [[पूरक (सेट सिद्धांत)]] नहीं है; केवल किनारे पूरक हैं।
  }}.</ref>  
 
पूरक ग्राफ का [[पूरक (सेट सिद्धांत)|पूरक सेट सिद्धांत]] नहीं होता है; केवल पूरक किनारे होते हैं।


== परिभाषा ==
== परिभाषा ==
होने देना {{math|1=''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'')}} एक साधारण ग्राफ बनो और चलो {{mvar|K}} के सभी 2-तत्व सबसेट से मिलकर बनता है {{mvar|V}}. तब {{math|1=''H''&nbsp;=&nbsp;(''V'',&nbsp;''K''&nbsp;\&nbsp;''E'')}} का पूरक है {{mvar|G}},<ref>{{Citation
मान लिया {{math|1=''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'')}} साधारण होते है और {{mvar|K}} में {{mvar|V}}. के सभी 2-तत्व उपसमुच्चय सम्मिलित होता है। तब {{math|1=''H''&nbsp;=&nbsp;(''V'',&nbsp;''K''&nbsp;\&nbsp;''E'')}} का पूरक {{mvar|G}} है ,<ref>{{Citation
| last=Diestel | first=Reinhard
| last=Diestel | first=Reinhard
| title=Graph Theory
| title=Graph Theory
Line 23: Line 25:
| edition=3rd
| edition=3rd
| isbn=3-540-26182-6
| isbn=3-540-26182-6
}}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref> कहाँ {{math|''K''&nbsp;\&nbsp;''E''}} का [[सापेक्ष पूरक]] है {{mvar|E}} में {{mvar|K}}. निर्देशित रेखांकन के लिए, पूरक को उसी तरह से परिभाषित किया जा सकता है, जैसे कि एक ही शीर्ष सेट पर एक [[निर्देशित ग्राफ]] के रूप में, सभी 2-तत्वों के आदेशित जोड़े के सेट का उपयोग करके {{mvar|V}} सेट के स्थान पर {{mvar|K}} उपरोक्त सूत्र में। ग्राफ के आसन्न मैट्रिक्स ए के संदर्भ में, यदि क्यू एक ही संख्या के शीर्षों के पूर्ण ग्राफ के आसन्न मैट्रिक्स है (यानी सभी प्रविष्टियां एकता हैं जो विकर्ण प्रविष्टियों को छोड़कर शून्य हैं), तो पूरक के आसन्न मैट्रिक्स ए क्यूए है।
}}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref> जहाँ {{math|''K''&nbsp;\&nbsp;''E''}} तथा {{mvar|E}} में {{mvar|K}}.का [[सापेक्ष पूरक|सापेक्ष पूरक होता]] है तथा निर्देशित रेखांकन के लिए, पूरक को उसी तरह से परिभाषित किया जा सकता है, जैसे कि एक ही शीर्ष सेट पर एक [[निर्देशित ग्राफ]] के रूप में, सभी 2-तत्वों के आदेशित जोड़े के सेट का उपयोग करके {{mvar|V}} सेट के स्थान पर {{mvar|K}} उपरोक्त सूत्र में उपयोग किया जाता हैं। ग्राफ के आसन्न आव्यूह ''A'' के संदर्भ में, यदि ''Q'' एक ही संख्या के शीर्षों के पूर्ण ग्राफ के आसन्न आव्यूह होता है, तथा पूरक के आसन्न आव्यूह  ''Q-A''.होता है।


[[मल्टीग्राफ]] के लिए पूरक को परिभाषित नहीं किया गया है। ग्राफ़ में जो लूप (ग्राफ़ सिद्धांत) की अनुमति देता है | स्वयं-लूप (लेकिन एकाधिक आसन्न नहीं) के पूरक {{mvar|G}} को प्रत्येक वर्टेक्स में एक सेल्फ-लूप जोड़कर परिभाषित किया जा सकता है जिसमें एक नहीं है {{mvar|G}}, और अन्यथा उपरोक्त के समान सूत्र का उपयोग करना। हालांकि, यह ऑपरेशन साधारण ग्राफ़ के लिए एक से अलग है, क्योंकि इसे बिना किसी सेल्फ-लूप वाले ग्राफ़ पर लागू करने से सभी कोने पर सेल्फ़-लूप वाला ग्राफ़ बन जाएगा।
[[मल्टीग्राफ]] के लिए पूरक को परिभाषित नहीं किया जाता है। ग्राफ़ में जो स्व-लूप की अनुमति देता है वो {{mvar|G}} के पूरक के प्रत्येक शीर्ष में एक स्व-लूप को जोड़कर परिभाषित किया जा सकता है जिसमें एक {{mvar|G}} नहीं होता है, और अन्यथा उपरोक्त के समान सूत्र का उपयोग करना चाहिए। यद्यपि, यह संक्रियाएं साधारण ग्राफ़ के लिए एक से भिन्न होती है, क्योंकि इसे बिना किसी स्वयं-लूप वाले ग्राफ़ पर प्रारंभ करने से सभी कोने पर स्वयं-लूप वाला ग्राफ़ बन जाता हैं।


== अनुप्रयोग और उदाहरण ==
== अनुप्रयोग और उदाहरण ==
पूरक के माध्यम से कई ग्राफ-सैद्धांतिक अवधारणाएं एक दूसरे से संबंधित हैं:
पूरक के माध्यम से कई ग्राफ-सैद्धांतिक अवधारणाएं एक दूसरे से संबंधित होता हैं:
*एक किनारे रहित ग्राफ का पूरक एक पूर्ण ग्राफ है और इसके विपरीत।
*एक किनारे रहित ग्राफ का पूरक एक पूर्ण ग्राफ होते है और इसके विपरीत अपूर्ण ग्राफ होता  है।
* किसी ग्राफ़ के पूरक ग्राफ़ का कोई [[प्रेरित सबग्राफ]]{{mvar|G}} इसी प्रेरित सबग्राफ का पूरक है {{mvar|G}}.
* किसी ग्राफ़ {{mvar|G}}  के पूरक ग्राफ़ का कोई [[प्रेरित सबग्राफ]] {{mvar|G}} में संबंधित प्रेरित सबग्राफ का पूरक होता है।
* एक ग्राफ में एक [[स्वतंत्र सेट (ग्राफ सिद्धांत)]] पूरक ग्राफ में एक क्लिक (ग्राफ सिद्धांत) है और इसके विपरीत। यह पिछले दो गुणों का एक विशेष मामला है, क्योंकि एक स्वतंत्र सेट एक एजलेस प्रेरित सबग्राफ है और एक क्लिक एक पूर्ण प्रेरित सबग्राफ है।
* एक ग्राफ में एक [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र सेट]] पूरक ग्राफ में एक गुट है और इसके विपरीत यह पिछले दो गुणों का एक विशेष स्थिति होती है, क्योंकि एक स्वतंत्र सेट एक धारहीन प्रेरित सबग्राफ होती है और एक क्लिक एक पूर्ण प्रेरित सबग्राफ होती है।
*ग्राफ़ का [[ग्राफ ऑटोमोर्फिज्म]] समूह इसके पूरक का ऑटोमोर्फिज़्म समूह है।
*ग्राफ़ का [[ग्राफ ऑटोमोर्फिज्म|ऑटोमोर्फिज्म]] समूह इसके पूरक का स्वसमाकृतिकता समूह होता है।
* प्रत्येक त्रिभुज-मुक्त ग्राफ़ का पूरक एक पंजा-मुक्त ग्राफ़ है,<ref>{{Citation
* प्रत्येक त्रिभुज-मुक्त ग्राफ़ का पूरक एक क्लॉ-फ्री ग्राफ होता है,<ref>{{Citation
  | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
  | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
  | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
  | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
Line 45: Line 47:
  | contribution-url = http://www.math.princeton.edu/~mchudnov/claws_survey.pdf
  | contribution-url = http://www.math.princeton.edu/~mchudnov/claws_survey.pdf
  | volume = 327
  | volume = 327
  | year = 2005}}..</ref> हालांकि उलटा सच नहीं है।
  | year = 2005}}..</ref>यद्यपि इसके विपरीत सत्य नहीं होता है।


== स्व-पूरक रेखांकन और ग्राफ वर्ग ==
== स्व-पूरक रेखांकन और ग्राफ वर्ग ==
[[File:Self-complementary NZ graph.svg|thumb|upright=0.65|चार-शीर्ष पथ स्व-पूरक है।]]
[[File:Self-complementary NZ graph.svg|thumb|upright=0.65|चार-शीर्ष पथ स्व-पूरक होते है।]]


{{main|Self-complementary graph}}
{{main|स्व-पूरक ग्राफ}}
एक [[स्व-पूरक ग्राफ]] एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के लिए [[ग्राफ समरूपता]] है।<ref name="bm"/>उदाहरणों में चार-वर्टेक्स [[पथ ग्राफ]]और पाँच-वर्टेक्स [[चक्र ग्राफ]]़ शामिल हैं। स्व-पूरक रेखांकन का कोई ज्ञात लक्षण वर्णन नहीं है।
एक [[स्व-पूरक ग्राफ]] एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के प्रति [[ग्राफ समरूपता|ग्राफ समरूप होता]] है।<ref name="bm"/>उदाहरणों में चार-शीर्ष [[पथ ग्राफ]] और पाँच-शीर्ष [[चक्र ग्राफ]] सम्मिलित होता हैं। स्व-पूरक रेखांकन का कोई ज्ञात लक्षण वर्णन नहीं होता है।


ग्राफ़ के कई वर्ग स्व-पूरक हैं, इस अर्थ में कि इनमें से किसी एक वर्ग में किसी भी ग्राफ़ का पूरक उसी वर्ग में एक और ग्राफ़ है।
ग्राफ़ के कई वर्ग स्व-पूरक हैं, इस अर्थ में कि इनमें से किसी एक वर्ग में किसी भी ग्राफ़ का पूरक उसी वर्ग में एक और ग्राफ़ देता है।
* सही रेखांकन वे रेखांकन होते हैं, जिनमें प्रत्येक प्रेरित सबग्राफ के लिए, वर्णिक संख्या अधिकतम क्लिक के आकार के बराबर होती है। तथ्य यह है कि एक [[बिल्कुल सही ग्राफ]] का पूरक भी सही है, लेज़्लो लोवाज़ का [[सही ग्राफ प्रमेय]] है।<ref>{{citation
* सही रेखांकन वे रेखांकन होते हैं, जिनमें प्रत्येक प्रेरित सबग्राफ के लिए, वर्णिक संख्या अधिकतम क्लिक के आकार के समान होती है। तथ्य यह है कि एक [[बिल्कुल सही ग्राफ|आदर्श ग्राफ]] का पूरक भी सही होता है,और लेज़्लो लोवाज़ का [[सही ग्राफ प्रमेय|आदर्श ग्राफ प्रमेय]] होते है।<ref>{{citation
  | last = Lovász | first = László | authorlink = László Lovász
  | last = Lovász | first = László | authorlink = László Lovász
  | year = 1972a
  | year = 1972a
Line 64: Line 66:
  | doi = 10.1016/0012-365X(72)90006-4| doi-access = free
  | doi = 10.1016/0012-365X(72)90006-4| doi-access = free
  }}.</ref>
  }}.</ref>
* [[कोग्राफ]] को ऐसे ग्राफ़ के रूप में परिभाषित किया जाता है, जिन्हें अलग-अलग संघ और पूरक संचालन द्वारा एकल कोने से बनाया जा सकता है। वे रेखांकन के एक स्व-पूरक परिवार का निर्माण करते हैं: किसी भी कॉग्राफ का पूरक एक और अलग कॉग्राफ है। एक से अधिक वर्टेक्स के कोग्राफ के लिए, प्रत्येक पूरक जोड़ी में बिल्कुल एक ग्राफ जुड़ा हुआ है, और कॉग्राफ की एक समकक्ष परिभाषा यह है कि उनके प्रत्येक जुड़े प्रेरित सबग्राफ में एक डिस्कनेक्ट पूरक है। एक और, स्व-पूरक परिभाषा यह है कि वे चार-शिखर पथ के रूप में बिना किसी प्रेरित सबग्राफ वाले ग्राफ़ हैं।<ref>{{Citation | last1=Corneil | first1=D. G. | author1-link = Derek Corneil | last2=Lerchs | first2=H. | last3=Stewart Burlingham | first3=L. | title=Complement reducible graphs | doi=10.1016/0166-218X(81)90013-5 | mr=0619603 | year=1981 | journal=[[Discrete Applied Mathematics]] | volume=3 | pages=163–174 | issue=3| doi-access=free }}.</ref>
* [[कोग्राफ]] को ऐसे ग्राफ़ के रूप में परिभाषित किया जाता है, जिन्हें भिन्न-भिन्न संघ और पूरक संचालन द्वारा एकल कोने से बनाया जा सकता है। वे रेखांकन के एक स्व-पूरक परिवार का निर्माण करते हैं: किसी भी कॉग्राफ का पूरक एक और भिन्न कॉग्राफ होता है। एक से अधिक शीर्ष के कोग्राफ के लिए, प्रत्येक पूरक जोड़ी में बिल्कुल एक ग्राफ जुड़ा हुआ है, और कॉग्राफ की एक समकक्ष परिभाषा यह है कि उनके प्रत्येक जुड़े प्रेरित सबग्राफ में एक डिस्कनेक्ट पूरक है। एक और, स्व-पूरक परिभाषा यह है कि वे चार-शिखर पथ के रूप में बिना किसी प्रेरित सबग्राफ वाले ग्राफ़ होते हैं।<ref>{{Citation | last1=Corneil | first1=D. G. | author1-link = Derek Corneil | last2=Lerchs | first2=H. | last3=Stewart Burlingham | first3=L. | title=Complement reducible graphs | doi=10.1016/0166-218X(81)90013-5 | mr=0619603 | year=1981 | journal=[[Discrete Applied Mathematics]] | volume=3 | pages=163–174 | issue=3| doi-access=free }}.</ref>
* रेखांकन का एक अन्य स्व-पूरक वर्ग विभाजन रेखांकन का वर्ग है, ऐसे रेखांकन जिनमें कोने को एक क्लिक और एक स्वतंत्र सेट में विभाजित किया जा सकता है। वही विभाजन पूरक ग्राफ में एक स्वतंत्र सेट और एक क्लिक देता है।<ref>{{citation
* रेखांकन का एक अन्य स्व-पूरक वर्ग विभाजन रेखांकन का वर्ग होता है, ऐसे रेखांकन जिनमें कोने को एक क्लिक और एक स्वतंत्र सेट में विभाजित किया जा सकता है। वही विभाजन पूरक ग्राफ में एक स्वतंत्र सेट और एक क्लिक देता है।<ref>{{citation
  | last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
  | last = Golumbic | first = Martin Charles | authorlink = Martin Charles Golumbic
  | title = Algorithmic Graph Theory and Perfect Graphs
  | title = Algorithmic Graph Theory and Perfect Graphs
Line 73: Line 75:
  | isbn = 0-12-289260-7
  | isbn = 0-12-289260-7
  | mr = 0562306}}.</ref>
  | mr = 0562306}}.</ref>
*[[दहलीज ग्राफ]] वे ग्राफ़ होते हैं जो बार-बार या तो एक स्वतंत्र वर्टेक्स (बिना किसी पड़ोसी के) या एक [[ सार्वभौमिक शिखर ]] (पहले से जोड़े गए सभी शीर्षों के निकट) को जोड़कर बनाए जाते हैं। ये दो ऑपरेशन पूरक हैं और वे रेखांकन का एक स्व-पूरक वर्ग उत्पन्न करते हैं।<ref>{{citation
*[[दहलीज ग्राफ|थ्रेशोल्ड ग्राफ]] वे ग्राफ़ होते हैं जो बार-बार या तो एक स्वतंत्र शीर्ष या एक [[ सार्वभौमिक शिखर ]] को जोड़कर बनाए जाते हैं। ये दो संक्रियाएं पूरक होते हैं और वे रेखांकन का एक स्व-पूरक वर्ग उत्पन्न करते हैं।<ref>{{citation
  | last1 = Golumbic | first1 = Martin Charles
  | last1 = Golumbic | first1 = Martin Charles
  | last2 = Jamison | first2 = Robert E.
  | last2 = Jamison | first2 = Robert E.
Line 84: Line 86:
  | volume = 52
  | volume = 52
  | year = 2006}}.</ref>
  | year = 2006}}.</ref>
 
== कलनविधि पक्ष ==
 
ग्राफ़ पर एल्गोरिदम के विश्लेषण में, एक ग्राफ़ और उसके पूरक के मध्य का अंतर एक महत्वपूर्ण अंतर है, क्योंकि एक [[विरल ग्राफ]] में सामान्य रूप से विरल पूरक नहीं होगा , और इसलिए एक कलनविधि जो किसी दिए गए ग्राफ़ पर किनारों की संख्या के अनुपात में समय लेता है, यदि उसी कलनविधि को पूरक ग्राफ़ के स्पष्ट प्रतिनिधित्व पर चलाया जाता है, तो बहुत अत्यधिक समय लग सकता है। इसलिए, शोधकर्ताओं ने एल्गोरिदम का अध्ययन किया है जो एक इनपुट ग्राफ के पूरक पर मानक ग्राफ संगणना करते हैं, एक [[निहित ग्राफ]] प्रतिनिधित्व का उपयोग करते हुए पूरक ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं होती है। विशेष रूप से, पूरक ग्राफ पर [[गहराई-पहली खोज]] या चौड़ाई-पहली खोज का अनुकरण करना संभव होता है, जो कि दिए गए ग्राफ के आकार में रैखिक होते है, भले ही पूरक ग्राफ का आकार बहुत बड़ा हो। .<ref name="iy98"/>पूरक ग्राफ की संयोजन से संबंधित अन्य गुणों की संगणना करने के लिए इन सिमुलेशन का उपयोग करना भी संभव होता है।<ref name="iy98">{{citation
== एल्गोरिथम पहलू ==
ग्राफ़ पर एल्गोरिदम के विश्लेषण में, एक ग्राफ़ और उसके पूरक के बीच का अंतर एक महत्वपूर्ण है, क्योंकि एक [[विरल ग्राफ]]़ (जोड़े के जोड़े की संख्या की तुलना में किनारों की एक छोटी संख्या के साथ) में सामान्य रूप से विरल पूरक नहीं होगा , और इसलिए एक एल्गोरिथम जो किसी दिए गए ग्राफ़ पर किनारों की संख्या के अनुपात में समय लेता है, यदि उसी एल्गोरिथम को पूरक ग्राफ़ के स्पष्ट प्रतिनिधित्व पर चलाया जाता है, तो बहुत अधिक समय लग सकता है। इसलिए, शोधकर्ताओं ने एल्गोरिदम का अध्ययन किया है जो एक इनपुट ग्राफ के पूरक पर मानक ग्राफ संगणना करते हैं, एक [[निहित ग्राफ]] प्रतिनिधित्व का उपयोग करते हुए पूरक ग्राफ के स्पष्ट निर्माण की आवश्यकता नहीं होती है। विशेष रूप से, पूरक ग्राफ पर [[गहराई-पहली खोज]] या चौड़ाई-पहली खोज का अनुकरण करना संभव है, जो कि दिए गए ग्राफ के आकार में रैखिक है, भले ही पूरक ग्राफ का आकार बहुत बड़ा हो। .<ref name="iy98"/>पूरक ग्राफ की कनेक्टिविटी से संबंधित अन्य गुणों की गणना करने के लिए इन सिमुलेशन का उपयोग करना भी संभव है।<ref name="iy98">{{citation
  | last1 = Ito | first1 = Hiro
  | last1 = Ito | first1 = Hiro
  | last2 = Yokoyama | first2 = Mitsuo
  | last2 = Yokoyama | first2 = Mitsuo
Line 109: Line 109:
  | volume = 2
  | volume = 2
  | year = 1999}}.</ref>
  | year = 1999}}.</ref>
==संदर्भ==
==संदर्भ==
{{reflist|30em}}
{{reflist|30em}}
[[Category: ग्राफ संचालन]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 01/05/2023]]
[[Category:Created On 01/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ग्राफ संचालन]]

Latest revision as of 10:38, 30 May 2023

पीटरसन ग्राफ बाईं ओर और इसका पूरक ग्राफ दाईं ओर होता हैं।

ग्राफ सिद्धांत के गणितीय क्षेत्र में, एक ग्राफ G का पूरक या व्युत्क्रम समान शीर्ष पर एक ग्राफ H होता है जैसे कि H दो भिन्न-भिन्न कोने सन्निकट होते हैं यद्यपि केवल G सन्निकट नहीं होते हैं .अर्थात्, एक ग्राफ़ के पूरक को एक संपूर्ण ग्राफ़ बनाने के लिए आवश्यक सभी लुप्त किनारों को भरता है, और उन सभी किनारों को हटा देता है जो पहले वहां थे।[1]

पूरक ग्राफ का पूरक सेट सिद्धांत नहीं होता है; केवल पूरक किनारे होते हैं।

परिभाषा

मान लिया G = (VE) साधारण होते है और K में V. के सभी 2-तत्व उपसमुच्चय सम्मिलित होता है। तब H = (VK \ 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. 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.
  2. Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6. Electronic edition, page 4.
  3. 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..
  4. 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.
  5. 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.
  6. Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, Theorem 6.1, p. 150, ISBN 0-12-289260-7, MR 0562306.
  7. 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. 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.
  9. 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.