बहुभुज-वृत्त ग्राफ
ग्राफ सिद्धांत के गणित अनुशासन में, एक बहुभुज-वृत्त ग्राफ उत्तल बहुभुजों के एक समूह का एक प्रतिच्छेदन ग्राफ है, जिसके सभी शीर्ष (ज्यामिति) एक सामान्य वृत्त पर स्थित हैं। इन ग्राफ़ को स्पाइडर ग्राफ़ भी कहा जाता है। ग्राफ के इस वर्ग को पहली बार 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.
