पूरक ग्राफ: 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 |
||
| 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|[[पीटरसन ग्राफ]] | [[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'' = (''V'', ''E'')}} साधारण है और {{mvar|K}} में {{mvar|V}}. के सभी 2-तत्व उपसमुच्चय सम्मिलित होता है। तब {{math|1=''H'' = (''V'', ''K'' \ ''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> | }}. [http://diestel-graph-theory.com/index.html Electronic edition], page 4.</ref> जहाँ {{math|''K'' \ ''E''}} में {{mvar|E}} में {{mvar|K}}.का [[सापेक्ष पूरक|सापेक्ष पूरक होता]] है तथा निर्देशित रेखांकन के लिए, पूरक को उसी तरह से परिभाषित किया जा सकता है, जैसे कि एक ही शीर्ष सेट पर एक [[निर्देशित ग्राफ]] के रूप में, सभी 2-तत्वों के आदेशित जोड़े के सेट का उपयोग करके {{mvar|V}} सेट के स्थान पर {{mvar|K}} उपरोक्त सूत्र में उपयोग किया जाता हैं। ग्राफ के आसन्न मैट्रिक्स ''A'' के संदर्भ में, यदि ''Q'' एक ही संख्या के शीर्षों के पूर्ण ग्राफ के आसन्न मैट्रिक्स है, तो पूरक के आसन्न मैट्रिक्स ''Q-A''.होता है। | ||
[[मल्टीग्राफ]] के लिए पूरक को परिभाषित नहीं किया गया है। ग्राफ़ में जो लूप | [[मल्टीग्राफ]] के लिए पूरक को परिभाषित नहीं किया गया है। ग्राफ़ में जो स्व-लूप की अनुमति देता है वो {{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| | {{main|स्व-पूरक ग्राफ}} | ||
एक [[स्व-पूरक ग्राफ]] एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के लिए [[ग्राफ समरूपता]] है।<ref name="bm"/>उदाहरणों में चार- | एक [[स्व-पूरक ग्राफ]] एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के लिए [[ग्राफ समरूपता|ग्राफ समरूप होता]] है।<ref name="bm"/>उदाहरणों में चार-शीर्ष [[पथ ग्राफ]] और पाँच-शीर्ष [[चक्र ग्राफ]] सम्मिलित होता हैं। स्व-पूरक रेखांकन का कोई ज्ञात लक्षण वर्णन नहीं होता है। | ||
ग्राफ़ के कई वर्ग स्व-पूरक हैं, इस अर्थ में कि इनमें से किसी एक वर्ग में किसी भी ग्राफ़ का पूरक उसी वर्ग में एक और ग्राफ़ है। | ग्राफ़ के कई वर्ग स्व-पूरक हैं, इस अर्थ में कि इनमें से किसी एक वर्ग में किसी भी ग्राफ़ का पूरक उसी वर्ग में एक और ग्राफ़ देता है। | ||
* सही रेखांकन वे रेखांकन होते हैं, जिनमें प्रत्येक प्रेरित सबग्राफ के लिए, वर्णिक संख्या अधिकतम क्लिक के आकार के | * सही रेखांकन वे रेखांकन होते हैं, जिनमें प्रत्येक प्रेरित सबग्राफ के लिए, वर्णिक संख्या अधिकतम क्लिक के आकार के समान होती है। तथ्य यह है कि एक [[बिल्कुल सही ग्राफ|आदर्श ग्राफ]] का पूरक भी सही होता है,और लेज़्लो लोवाज़ का [[सही ग्राफ प्रमेय]] है।<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 | * रेखांकन का एक अन्य स्व-पूरक वर्ग विभाजन रेखांकन का वर्ग होता है, ऐसे रेखांकन जिनमें कोने को एक क्लिक और एक स्वतंत्र सेट में विभाजित किया जा सकता है। वही विभाजन पूरक ग्राफ में एक स्वतंत्र सेट और एक क्लिक देता है।<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 | ||
| 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 | ||
| 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}} | ||
Revision as of 15:48, 14 May 2023
पीटरसन ग्राफ बाईं ओर और इसका पूरक ग्राफ दाईं ओर होता हैं।
ग्राफ सिद्धांत के गणितीय क्षेत्र में, एक ग्राफ 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.
