पूरक ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 18: | Line 18: | ||
== परिभाषा == | == परिभाषा == | ||
मान लिया {{math|1=''G'' = (''V'', ''E'')}} साधारण है और {{mvar|K}} में {{mvar|V}}. के सभी 2-तत्व उपसमुच्चय सम्मिलित होता है। तब {{math|1=''H'' = (''V'', ''K'' \ ''E'')}} का {{mvar|G}} | मान लिया {{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 25: | 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'' \ ''E''}} | }}. [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}} में संबंधित प्रेरित सबग्राफ का पूरक होता है। | * किसी ग्राफ़ {{mvar|G}} के पूरक ग्राफ़ का कोई [[प्रेरित सबग्राफ]] {{mvar|G}} में संबंधित प्रेरित सबग्राफ का पूरक होता है। | ||
* एक ग्राफ में एक [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र सेट]] पूरक ग्राफ में एक गुट है और इसके विपरीत यह पिछले दो गुणों का एक विशेष स्थिति होती है, क्योंकि एक स्वतंत्र सेट एक | * एक ग्राफ में एक [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र सेट]] पूरक ग्राफ में एक गुट है और इसके विपरीत यह पिछले दो गुणों का एक विशेष स्थिति होती है, क्योंकि एक स्वतंत्र सेट एक धारहीन प्रेरित सबग्राफ होती है और एक क्लिक एक पूर्ण प्रेरित सबग्राफ होती है। | ||
*ग्राफ़ का [[ग्राफ ऑटोमोर्फिज्म|ऑटोमोर्फिज्म]] समूह इसके पूरक का | *ग्राफ़ का [[ग्राफ ऑटोमोर्फिज्म|ऑटोमोर्फिज्म]] समूह इसके पूरक का स्वसमाकृतिकता समूह होता है। | ||
* प्रत्येक त्रिभुज-मुक्त ग्राफ़ का पूरक एक | * प्रत्येक त्रिभुज-मुक्त ग्राफ़ का पूरक एक क्लॉ-फ्री ग्राफ होता है,<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 53: | Line 53: | ||
{{main|स्व-पूरक ग्राफ}} | {{main|स्व-पूरक ग्राफ}} | ||
एक [[स्व-पूरक ग्राफ]] एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के | एक [[स्व-पूरक ग्राफ]] एक ऐसा ग्राफ है जो अपने स्वयं के पूरक के प्रति [[ग्राफ समरूपता|ग्राफ समरूप होता]] है।<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 86: | 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 111: | Line 111: | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist|30em}} | {{reflist|30em}} | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category: | |||
[[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 = (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.
