बहुभुज-वृत्त ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{redirect|स्पाइडर रेखांकन|आरेख|रडार चार्ट|क्रिकेट शब्द|Glossary of cricket terms}} | {{redirect|स्पाइडर रेखांकन|आरेख|रडार चार्ट|क्रिकेट शब्द|Glossary of cricket terms}} | ||
[[File:Polygon-circle graph.svg|thumb|right|400px|{{center|बाईं ओर एक वृत्त में खुदे हुए बहुभुजों का एक समूह; दाईं ओर सापेक्ष '''बहुभुज-वृत्त रेखांकन''' (बहुभुजों का प्रतिच्छेदन रेखांकन)।<br> तल पर वृत्त के चारों ओर बहुभुजों का वैकल्पिक क्रम।}}]][[ग्राफ सिद्धांत|रेखांकन सिद्धांत]] के गणित अनुशासन में, | [[File:Polygon-circle graph.svg|thumb|right|400px|{{center|बाईं ओर एक वृत्त में खुदे हुए बहुभुजों का एक समूह; दाईं ओर सापेक्ष '''बहुभुज-वृत्त रेखांकन''' (बहुभुजों का प्रतिच्छेदन रेखांकन)।<br> तल पर वृत्त के चारों ओर बहुभुजों का वैकल्पिक क्रम।}}]][[ग्राफ सिद्धांत|रेखांकन सिद्धांत]] के गणित अनुशासन में, बहुभुज-वृत्त रेखांकन [[उत्तल बहुभुज]] के समूह का प्रतिच्छेदन रेखांकन है | जिसके सभी शीर्ष (ज्यामिति) सामान्य वृत्त पर स्थित हैं। इन रेखांकन को तंतु रेखांकन भी कहा जाता है। रेखांकन के इस वर्ग को पहली बार 1988 में [[माइकल फेलो]] द्वारा सुझाया गया था | इस तथ्य से प्रेरित होकर कि यह किनारे के संकुचन और [[प्रेरित सबग्राफ|प्रेरित सबरेखांकन]] संचालन के अनुसार बंद है।<ref name="kp">{{citation | ||
| last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl | | last1 = Kratochvíl | first1 = Jan | author1-link = Jan Kratochvíl | ||
| last2 = Pergel | first2 = Martin | | last2 = Pergel | first2 = Martin | ||
| Line 15: | Line 15: | ||
}}.</ref> | }}.</ref> | ||
बहुभुज-वृत्त रेखांकन को वैकल्पिक क्रम के रूप में दर्शाया जा सकता है। इस तरह के अनुक्रम को रेखांकन (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को हानि पहुचा कर प्राप्त किया जा सकता है | जिससे कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए सूचीबद्ध करें (परिपत्र क्रम में,इचानुसार बिंदु से प्रारंभ) बहुभुज उस शीर्ष से जुड़ा हुआ है। | बहुभुज-वृत्त रेखांकन को वैकल्पिक क्रम के रूप में दर्शाया जा सकता है। इस तरह के अनुक्रम को रेखांकन (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को हानि पहुचा कर प्राप्त किया जा सकता है | जिससे कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए सूचीबद्ध करें (परिपत्र क्रम में,इचानुसार बिंदु से प्रारंभ) बहुभुज उस शीर्ष से जुड़ा हुआ है। | ||
== उत्प्रेरित अवयस्कों के अंतर्गत बंद == | == उत्प्रेरित अवयस्कों के अंतर्गत बंद == | ||
बहुभुज-वृत्त रेखांकन के किनारों के सिकुड़ने से एक और बहुभुज-वृत्त रेखांकन बनता है। नए रेखांकन का | बहुभुज-वृत्त रेखांकन के किनारों के सिकुड़ने से एक और बहुभुज-वृत्त रेखांकन बनता है। नए रेखांकन का ज्यामितीय प्रतिनिधित्व उनके उत्तल पतवार द्वारा अनुबंधित किनारे के दो समापन बिंदुओं के अनुरूप बहुभुजों को बदलकर बनाया जा सकता है। वैकल्पिक रूप से, मूल रेखांकन का प्रतिनिधित्व करने वाले वैकल्पिक अनुक्रम में, अनुबंधित किनारे के समापन बिंदुओं को एकल अनुक्रम में दर्शाने वाले अनुक्रमों को जोड़कर अनुबंधित रेखांकन के वैकल्पिक अनुक्रम प्रतिनिधित्व का उत्पादन होता है। बहुभुज-वृत्त रेखांकन भी प्रेरित सबरेखांकन या समकक्ष शीर्ष विलोपन संचालन के अनुसार बंद होते हैं: | शीर्ष को हटाने के लिए, इसके बहुभुज को ज्यामितीय प्रतिनिधित्व से हटा दें, या वैकल्पिक क्रम से इसके बिंदुओं को हटा देते है | | ||
== मान्यता == | == मान्यता == | ||
एम. कोएबे ने | एम. कोएबे ने बहुपद समय पहचान एल्गोरिदम की घोषणा की थी |,<ref>{{citation | ||
| last = Koebe | first = Manfred | | last = Koebe | first = Manfred | ||
| contribution = On a new class of intersection graphs | | contribution = On a new class of intersection graphs | ||
| Line 42: | Line 39: | ||
| url = https://books.google.com/books/about/Efficient_Graph_Representations.html?id=RrtXSKMAmWgC&pg=PA41 | | url = https://books.google.com/books/about/Efficient_Graph_Representations.html?id=RrtXSKMAmWgC&pg=PA41 | ||
| volume = 19 | | volume = 19 | ||
| year = 2003}}.</ref> और | | year = 2003}}.</ref> और अंतिम संस्करण कभी प्रकाशित नहीं हुआ था। <ref name="kp"/> मार्टिन पर्गेल ने बाद में सिद्ध किया कि इन रेखांकनों को पहचानने की समस्या एनपी-पूर्ण है।<ref>{{citation | ||
| last = Pergel | first = Martin | | last = Pergel | first = Martin | ||
| contribution = Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete | | contribution = Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete | ||
| Line 52: | Line 49: | ||
| title = Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers | | title = Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers | ||
| volume = 4769 | | volume = 4769 | ||
| year = 2007}}.</ref> यह निर्धारित करने के लिए एनपी-पूर्ण भी है कि किसी दिए गए रेखांकन को बहुभुज-वृत्त रेखांकन के रूप में अधिक से अधिक प्रदर्शित किया जा सकता है | जिसमे किसी भी {{math|''k'' ≥ 3}} | | year = 2007}}.</ref> यह निर्धारित करने के लिए एनपी-पूर्ण भी है कि किसी दिए गए रेखांकन को बहुभुज-वृत्त रेखांकन के रूप में अधिक से अधिक प्रदर्शित किया जा सकता है | जिसमे किसी भी {{math|''k'' ≥ 3}} के लिए प्रति बहुभुज अधिकतम {{mvar|k}} शीर्ष होते है |<ref name="kp"/> | ||
== संबंधित रेखांकन समूह == | == संबंधित रेखांकन समूह == | ||
बहुभुज-वृत्त रेखांकन वृत्त रेखांकन का | बहुभुज-वृत्त रेखांकन वृत्त रेखांकन का सामान्यीकरण है,| जो वृत्त के जीवाओं के प्रतिच्छेदन रेखांकन हैं, और [[ट्रेपेज़ॉइड ग्राफ|चतुर्भुज]] रेखांकन, चतुर्भुज के प्रतिच्छेदन के रेखांकन हैं | जो सभी समान दो समानांतर रेखाओं पर उनके कोने हैं। इनमें [[गोलाकार चाप ग्राफ|गोलाकार चाप रेखांकन]] भी सम्मिलित हैं। <ref name="kp"/><ref>[http://www.graphclasses.org/classes/gc_536.html Spider graphs], Information System on Graph Classes and their Inclusions, retrieved 2016-07-11.</ref> | ||
बहुभुज-वृत्त रेखांकन, सामान्यतः, पूर्ण रेखांकन नहीं होते हैं | किन्तु वे निकट-परिपूर्ण होते हैं, इस अर्थ में कि उनके रंगीन नंबरों को उनके [[ गुट संख्या | गुट संख्या]] के | बहुभुज-वृत्त रेखांकन, सामान्यतः, पूर्ण रेखांकन नहीं होते हैं | किन्तु वे निकट-परिपूर्ण होते हैं, इस अर्थ में कि उनके रंगीन नंबरों को उनके [[ गुट संख्या |गुट संख्या]] के (घातीय) फलन द्वारा बाध्य किया जा सकता है।<ref>{{citation | ||
| last1 = Kostochka | first1 = Alexandr | | last1 = Kostochka | first1 = Alexandr | ||
| last2 = Kratochvíl | first2 = Jan | author2-link = Jan Kratochvíl | | last2 = Kratochvíl | first2 = Jan | author2-link = Jan Kratochvíl | ||
| Line 68: | Line 65: | ||
| year = 1997| doi-access = free | | year = 1997| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
Revision as of 09:54, 29 April 2023
रेखांकन सिद्धांत के गणित अनुशासन में, बहुभुज-वृत्त रेखांकन उत्तल बहुभुज के समूह का प्रतिच्छेदन रेखांकन है | जिसके सभी शीर्ष (ज्यामिति) सामान्य वृत्त पर स्थित हैं। इन रेखांकन को तंतु रेखांकन भी कहा जाता है। रेखांकन के इस वर्ग को पहली बार 1988 में माइकल फेलो द्वारा सुझाया गया था | इस तथ्य से प्रेरित होकर कि यह किनारे के संकुचन और प्रेरित सबरेखांकन संचालन के अनुसार बंद है।[1]
बहुभुज-वृत्त रेखांकन को वैकल्पिक क्रम के रूप में दर्शाया जा सकता है। इस तरह के अनुक्रम को रेखांकन (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को हानि पहुचा कर प्राप्त किया जा सकता है | जिससे कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए सूचीबद्ध करें (परिपत्र क्रम में,इचानुसार बिंदु से प्रारंभ) बहुभुज उस शीर्ष से जुड़ा हुआ है।
उत्प्रेरित अवयस्कों के अंतर्गत बंद
बहुभुज-वृत्त रेखांकन के किनारों के सिकुड़ने से एक और बहुभुज-वृत्त रेखांकन बनता है। नए रेखांकन का ज्यामितीय प्रतिनिधित्व उनके उत्तल पतवार द्वारा अनुबंधित किनारे के दो समापन बिंदुओं के अनुरूप बहुभुजों को बदलकर बनाया जा सकता है। वैकल्पिक रूप से, मूल रेखांकन का प्रतिनिधित्व करने वाले वैकल्पिक अनुक्रम में, अनुबंधित किनारे के समापन बिंदुओं को एकल अनुक्रम में दर्शाने वाले अनुक्रमों को जोड़कर अनुबंधित रेखांकन के वैकल्पिक अनुक्रम प्रतिनिधित्व का उत्पादन होता है। बहुभुज-वृत्त रेखांकन भी प्रेरित सबरेखांकन या समकक्ष शीर्ष विलोपन संचालन के अनुसार बंद होते हैं: | शीर्ष को हटाने के लिए, इसके बहुभुज को ज्यामितीय प्रतिनिधित्व से हटा दें, या वैकल्पिक क्रम से इसके बिंदुओं को हटा देते है |
मान्यता
एम. कोएबे ने बहुपद समय पहचान एल्गोरिदम की घोषणा की थी |,[2] चूँकि उनके प्रारंभिक संस्करण में गंभीर त्रुटियाँ थीं |[3] और अंतिम संस्करण कभी प्रकाशित नहीं हुआ था। [1] मार्टिन पर्गेल ने बाद में सिद्ध किया कि इन रेखांकनों को पहचानने की समस्या एनपी-पूर्ण है।[4] यह निर्धारित करने के लिए एनपी-पूर्ण भी है कि किसी दिए गए रेखांकन को बहुभुज-वृत्त रेखांकन के रूप में अधिक से अधिक प्रदर्शित किया जा सकता है | जिसमे किसी भी k ≥ 3 के लिए प्रति बहुभुज अधिकतम k शीर्ष होते है |[1]
संबंधित रेखांकन समूह
बहुभुज-वृत्त रेखांकन वृत्त रेखांकन का सामान्यीकरण है,| जो वृत्त के जीवाओं के प्रतिच्छेदन रेखांकन हैं, और चतुर्भुज रेखांकन, चतुर्भुज के प्रतिच्छेदन के रेखांकन हैं | जो सभी समान दो समानांतर रेखाओं पर उनके कोने हैं। इनमें गोलाकार चाप रेखांकन भी सम्मिलित हैं। [1][5]
बहुभुज-वृत्त रेखांकन, सामान्यतः, पूर्ण रेखांकन नहीं होते हैं | किन्तु वे निकट-परिपूर्ण होते हैं, इस अर्थ में कि उनके रंगीन नंबरों को उनके गुट संख्या के (घातीय) फलन द्वारा बाध्य किया जा सकता है।[6]
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Kratochvíl, Jan; Pergel, Martin (2004), "Two results on intersection graphs of polygons", Graph Drawing: 11th International Symposium, GD 2003 Perugia, Italy, September 21-24, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2912, Berlin: Springer, pp. 59–70, doi:10.1007/978-3-540-24595-7_6, MR 2177583.
- ↑ Koebe, Manfred (1992), "On a new class of intersection graphs", Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), Ann. Discrete Math., vol. 51, North-Holland, Amsterdam, pp. 141–143, doi:10.1016/S0167-5060(08)70618-6, MR 1206256.
- ↑ Spinrad, Jeremy P. (2003), Efficient graph representations, Fields Institute Monographs, vol. 19, American Mathematical Society, Providence, RI, p. 41, ISBN 0-8218-2815-0, MR 1971502.
- ↑ Pergel, Martin (2007), "Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete", Graph-Theoretic Concepts in Computer Science: 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007, Revised Papers, Lecture Notes in Computer Science, vol. 4769, Berlin: Springer, pp. 238–247, doi:10.1007/978-3-540-74839-7_23, MR 2428581.
- ↑ Spider graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-07-11.
- ↑ Kostochka, Alexandr; Kratochvíl, Jan (1997), "Covering and coloring polygon-circle graphs", Discrete Mathematics, 163 (1–3): 299–305, doi:10.1016/S0012-365X(96)00344-5, MR 1428585.
