बहुभुज-वृत्त ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{redirect|Spider graph|the chart|radar chart|the cricket term|Glossary of cricket terms}} | {{redirect|Spider graph|the chart|radar chart|the cricket term|Glossary of cricket terms}} | ||
[[File:Polygon-circle graph.svg|thumb|right|400px|{{center|On the left a set of polygons inscribed in a circle; on the right the relative '''Polygon-circle graph''' (intersection graph of the polygons).<br> On the bottom the alternating sequence of polygons around the circle.}}]][[ग्राफ सिद्धांत]] के गणित अनुशासन में, बहुभुज-वृत्त | [[File:Polygon-circle graph.svg|thumb|right|400px|{{center|On the left a set of polygons inscribed in a circle; on the right the relative '''Polygon-circle graph''' (intersection graph of the polygons).<br> On the bottom the alternating sequence of polygons around the circle.}}]][[ग्राफ सिद्धांत|रेखांकन सिद्धांत]] के गणित अनुशासन में, बहुभुज-वृत्त रेखांकन [[उत्तल बहुभुज]] के समूह का प्रतिच्छेदन रेखांकन है | जिसके सभी शीर्ष (ज्यामिति) सामान्य वृत्त पर स्थित हैं। इन रेखांकन को तंतु रेखांकन भी कहा जाता है। रेखांकन के इस वर्ग को पहली बार 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 14: | Line 14: | ||
| year = 2004| doi-access = free | | year = 2004| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
बहुभुज-वृत्त | बहुभुज-वृत्त रेखांकन को वैकल्पिक क्रम के रूप में दर्शाया जा सकता है। इस तरह के अनुक्रम को रेखांकन (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को हानि पहुचा कर प्राप्त किया जा सकता है | जिससे कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए सूचीबद्ध करें (परिपत्र क्रम में,इचानुसार बिंदु से प्रारंभ) बहुभुज उस शीर्ष से जुड़ा हुआ है। | ||
'''इस तरह के अनुक्रम को | '''इस तरह के अनुक्रम को रेखांकन (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को परेशान करके प्राप्त किया जा सकता है जिससे कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए''' | ||
== | == उत्प्रेरित अवयस्कों के अंतर्गत बंद == | ||
बहुभुज-वृत्त रेखांकन के किनारों के सिकुड़ने से एक और बहुभुज-वृत्त रेखांकन बनता है। नए रेखांकन का ज्यामितीय प्रतिनिधित्व उनके उत्तल पतवार द्वारा अनुबंधित किनारे के दो समापन बिंदुओं के अनुरूप बहुभुजों को बदलकर बनाया जा सकता है। वैकल्पिक रूप से, मूल रेखांकन का प्रतिनिधित्व करने वाले वैकल्पिक अनुक्रम में, अनुबंधित किनारे के समापन बिंदुओं को एकल अनुक्रम में दर्शाने वाले अनुक्रमों को जोड़कर अनुबंधित रेखांकन के वैकल्पिक अनुक्रम प्रतिनिधित्व का उत्पादन होता है। बहुभुज-वृत्त रेखांकन भी प्रेरित सबरेखांकन या समकक्ष शीर्ष विलोपन ऑपरेशंस के अनुसार बंद होते हैं: | शीर्ष को हटाने के लिए, इसके बहुभुज को ज्यामितीय प्रतिनिधित्व से हटा दें, या वैकल्पिक क्रम से इसके बिंदुओं को हटा दें। | |||
== मान्यता == | == मान्यता == | ||
एम. कोएबे ने बहुपद समय पहचान एल्गोरिदम की घोषणा की,<ref>{{citation | एम. कोएबे ने बहुपद समय पहचान एल्गोरिदम की घोषणा की थी |,<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 32: | Line 32: | ||
| title = Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990) | | title = Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990) | ||
| volume = 51 | | volume = 51 | ||
| year = 1992}}.</ref> | | year = 1992}}.</ref> चूँकि उनके प्रारंभिक संस्करण में गंभीर त्रुटियाँ थीं |<ref>{{citation | ||
| last = Spinrad | first = Jeremy P. | | last = Spinrad | first = Jeremy P. | ||
| isbn = 0-8218-2815-0 | | isbn = 0-8218-2815-0 | ||
| Line 42: | Line 42: | ||
| 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> और अंतिम संस्करण कभी प्रकाशित नहीं हुआ था।<ref name="kp"/>मार्टिन पर्गेल ने बाद में | | 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 52: | ||
| 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> | | 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 70: | Line 68: | ||
| year = 1997| doi-access = free | | year = 1997| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
Revision as of 09:48, 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.
