बहुभुज-वृत्त ग्राफ: Difference between revisions
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 | ||
| 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 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> और | | 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 57: | Line 57: | ||
== संबंधित ग्राफ परिवार == | == संबंधित ग्राफ परिवार == | ||
बहुभुज-वृत्त ग्राफ़ वृत्त ग्राफ़ का | बहुभुज-वृत्त ग्राफ़ वृत्त ग्राफ़ का सामान्यीकरण है, जो वृत्त के जीवाओं के प्रतिच्छेदन ग्राफ़ हैं, और [[ट्रेपेज़ॉइड ग्राफ]]़, ट्रेपेज़ॉइड के चौराहे के ग्राफ़ हैं जो सभी समान दो समानांतर रेखाओं पर उनके कोने हैं। इनमें [[गोलाकार चाप ग्राफ]] भी शामिल हैं।<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 | ||
Revision as of 09:29, 29 April 2023
ग्राफ सिद्धांत के गणित अनुशासन में, बहुभुज-वृत्त ग्राफ उत्तल बहुभुजों के समूह का प्रतिच्छेदन ग्राफ है, जिसके सभी शीर्ष (ज्यामिति) सामान्य वृत्त पर स्थित हैं। इन ग्राफ़ को स्पाइडर ग्राफ़ भी कहा जाता है। ग्राफ के इस वर्ग को पहली बार 1988 में माइकल फेलो द्वारा सुझाया गया था, इस तथ्य से प्रेरित होकर कि यह किनारे के संकुचन और प्रेरित सबग्राफ संचालन के तहत बंद है।[1]
बहुभुज-वृत्त ग्राफ को वैकल्पिक क्रम के रूप में दर्शाया जा सकता है। इस तरह के अनुक्रम को ग्राफ़ (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को परेशान करके प्राप्त किया जा सकता है ताकि कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए सूचीबद्ध करें (परिपत्र क्रम में, मनमाना बिंदु से शुरू) बहुभुज उस शीर्ष से जुड़ा हुआ है।
इस तरह के अनुक्रम को ग्राफ़ (यदि आवश्यक हो) का प्रतिनिधित्व करने वाले बहुभुजों को परेशान करके प्राप्त किया जा सकता है ताकि कोई दो शीर्ष साझा न करें, और उसके बाद प्रत्येक शीर्ष के लिए
प्रेरित नाबालिगों के तहत बंद
पॉलीगॉन-सर्कल ग्राफ़ के किनारों के सिकुड़ने से एक और पॉलीगॉन-सर्कल ग्राफ़ बनता है। नए ग्राफ का ज्यामितीय प्रतिनिधित्व उनके उत्तल पतवार द्वारा अनुबंधित किनारे के दो समापन बिंदुओं के अनुरूप बहुभुजों को बदलकर बनाया जा सकता है। वैकल्पिक रूप से, मूल ग्राफ़ का प्रतिनिधित्व करने वाले वैकल्पिक अनुक्रम में, अनुबंधित किनारे के समापन बिंदुओं को एकल अनुक्रम में दर्शाने वाले अनुक्रमों को जोड़कर अनुबंधित ग्राफ़ के वैकल्पिक अनुक्रम प्रतिनिधित्व का उत्पादन होता है। पॉलीगॉन सर्कल ग्राफ़ भी प्रेरित सबग्राफ या समकक्ष वर्टेक्स विलोपन ऑपरेशंस के तहत बंद होते हैं: वर्टेक्स को हटाने के लिए, इसके बहुभुज को ज्यामितीय प्रतिनिधित्व से हटा दें, या वैकल्पिक क्रम से इसके बिंदुओं को हटा दें।
मान्यता
एम. कोएबे ने बहुपद समय पहचान एल्गोरिदम की घोषणा की,[2] हालाँकि उनके प्रारंभिक संस्करण में गंभीर त्रुटियाँ थीं[3] और अंतिम संस्करण कभी प्रकाशित नहीं हुआ था।[1]मार्टिन पर्गेल ने बाद में साबित किया कि इन ग्राफों को पहचानने की समस्या एनपी-पूर्ण है।[4] यह निर्धारित करने के लिए एनपी-पूर्ण भी है कि किसी दिए गए ग्राफ़ को बहुभुज-वृत्त ग्राफ़ के रूप में अधिक से अधिक प्रदर्शित किया जा सकता है या नहीं k शीर्ष प्रति बहुभुज, किसी के लिए भी k ≥ 3.[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.
