आउटरप्लानर ग्राफ
ग्राफ़ सिद्धांत में, एक आउटरप्लानर ग्राफ़ एक ग्राफ़ होता है जिसमें एक प्लैनर आरेखण होता है जिसके लिए सभी कोने आरेखण के बाहरी चेहरे से संबंधित होते हैं।
आउटर प्लेनर ग्राफ को दो वर्जित अवयस्क K4 और K2,3, या उनके कॉलिन डी वेर्डिएर ग्राफ़ इनवेरिएंट द्वारा (प्लैनर ग्राफ़ के लिए वैगनर के प्रमेय के अनुरूप) चित्रित किया जा सकता है।
उनके पास हैमिल्टनियन चक्र हैं यदि और केवल यदि वे द्विसंबद्ध हैं, तो इस मामले में बाहरी चेहरा अद्वितीय हैमिल्टनियन चक्र बनाता है। प्रत्येक आउटरप्लानर ग्राफ 3-रंगीन है, और अधिकतम 2 में गिरावट और पेड़ की चौड़ाई है।
बाहरी प्लैनर ग्राफ़ प्लानर ग्राफ़ का एक सबसेट है, श्रृंखला-समानांतर ग्राफ़ के सबग्राफ और सर्कल ग्राफ हैं। अधिक से अधिक बाहरी ग्राफ़र ग्राफ़, जिनके लिए बाहरी किनारों को संरक्षित करते समय कोई और किनारों को जोड़ा नहीं जा सकता है, वे कॉर्डल ग्राफ और दृश्यता ग्राफ भी हैं।
इतिहास
बेस ग्राफ की दो प्रतियों को जोड़ने के लिए एक परिपूर्ण मिलान का उपयोग करके बनाए गए ग्राफ की योजना का निर्धारण करने की समस्या के संबंध में, चार्ट्रैंड & एंड हैरी (1967) द्वारा आउटरप्लानर ग्राफ़ का अध्ययन और नामकरण किया गया था (उदाहरण के लिए, सामान्यीकृत पीटरसन ग्राफ में से कई एक चक्र ग्राफ की दो प्रतियों से इस प्रकार बनते हैं)। जैसा कि उन्होंने दिखाया, जब आधार ग्राफ द्विसंबद्ध ग्राफ होता है, तो इस तरह से निर्मित एक ग्राफ प्लानर होता है यदि और केवल अगर इसका आधार ग्राफ आउटरप्लानर होता है और मिलान इसके बाहरी चक्र का एक डायहेड्रल समूह क्रमचय बनाता है। चार्ट्रैंड और हैरी ने आउटरप्लानर ग्राफ के लिए कुराटोव्स्की के प्रमेय का एक एनालॉग भी साबित किया, कि एक ग्राफ आउटरप्लानर है अगर और केवल अगर इसमें दो ग्राफ K4 या K2,3 में से एक का उपखंड नहीं है।
परिभाषा और लक्षण वर्णन
एक आउटरप्लानर ग्राफ एक अप्रत्यक्ष ग्राफ है जो यूक्लिडियन विमान में क्रॉसिंग संख्या (ग्राफ सिद्धांत) के बिना ग्राफ एम्बेडिंग हो सकता है, इस तरह से कि सभी कोने ड्राइंग के अनबाउंड चेहरे से संबंधित हैं। अर्थात् कोई भी शीर्ष किनारों से पूरी तरह घिरा नहीं है। वैकल्पिक रूप से, एक ग्राफ जी बाहरी प्लानर है यदि जी से एक नया वर्टेक्स जोड़कर बनाया गया ग्राफ, किनारों के साथ इसे अन्य सभी शिखरों से जोड़ता है, एक प्लानर ग्राफ है।[1] एक मैक्सिमम आउटरप्लानर ग्राफ एक आउटरप्लानर ग्राफ है जिसमें आउटरप्लानरिटी को संरक्षित करते हुए इसमें कोई अतिरिक्त किनारा नहीं जोड़ा जा सकता है। n शीर्षों वाले प्रत्येक अधिकतम बाह्यप्लानर ग्राफ़ में वास्तव में 2n − 3 किनारे होते हैं, और अधिकतम बाह्यप्लानर ग्राफ़ का प्रत्येक परिबद्ध फलक एक त्रिभुज होता है।
एक आउटरप्लानर ग्राफ एक अप्रत्यक्ष ग्राफ है जिसे बिना क्रॉसिंग संख्या (ग्राफ सिद्धांत) के यूक्लिडियन विमान में खींचा जा सकता है ताकि सभी कोने ड्राइंग के अनबाउंड चेहरे से संबंधित हों। अर्थात् कोई भी शीर्ष किनारों से पूरी तरह घिरा नहीं है। वैकल्पिक रूप से, एक ग्राफ G बाहरीप्लानर होता है यदि G से एक नया शीर्ष जोड़कर बनाया गया ग्राफ, किनारों के साथ इसे अन्य सभी शीर्षों से जोड़ता है, एक प्लानर ग्रैप है।[1]
एक मैक्सिमम आउटरप्लानर ग्राफ एक आउटरप्लानर ग्राफ है जिसमें आउटरप्लानरिटी को संरक्षित करते हुए इसमें कोई अतिरिक्त किनारा नहीं जोड़ा जा सकता है। एन कोने के साथ प्रत्येक अधिकतम बाहरी ग्राफ़र में बिल्कुल 2n - 3 किनारे हैं, और एक अधिकतम बाहरी ग्राफ़ का प्रत्येक घिरा हुआ चेहरा एक त्रिकोण है।
निषिद्ध रेखांकन
आउटरप्लानर ग्राफ़ में कुराटोस्की के प्रमेय और प्लानर ग्राफ़ के लिए वैगनर के प्रमेय के अनुरूप वर्जित ग्राफ़ लक्षण वर्णन है: एक ग्राफ बाहरी है अगर और केवल अगर इसमें पूर्ण ग्राफ K4 या पूर्ण द्विदलीय ग्राफ K2,3 का उपखंड नहीं है।[2] वैकल्पिक रूप से, एक ग्राफ आउटरप्लानर है अगर और केवल अगर इसमें K4 या K2,3 एक नाबालिग (ग्राफ सिद्धांत) के रूप में शामिल नहीं है, तो किनारों को हटाकर और अनुबंधित करके एक ग्राफ प्राप्त किया जाता है।[3]
एक त्रिभुज-मुक्त ग्राफ बाहरीप्लानर है अगर और केवल अगर इसमें K2,3 का उपखंड नहीं है।[4]
कॉलिन डी वर्डीयर अपरिवर्तनीय
एक ग्राफ़ आउटरप्लानर होता है अगर और केवल अगर इसका कॉलिन डी वेर्डिएर ग्राफ़ इनवेरिएंट अधिकतम दो हो। एक, तीन, या चार में कॉलिन डी वेर्डिएर अपरिवर्तनीय होने के समान तरीके से वर्णित ग्राफ़ क्रमशः रैखिक वन, प्लानर ग्राफ़ और लिंक रहित एम्बेडिंग करने योग्य ग्राफ़ हैं।
गुण
बाइकनेक्टिविटी और हैमिल्टनिस
एक आउटरप्लानर ग्राफ़ द्विसंबद्ध होता है यदि और केवल अगर ग्राफ़ का बाहरी फलक दोहराए गए शीर्षों के बिना एक सरल चक्र (ग्राफ़ सिद्धांत) बनाता है। एक आउटरप्लानर ग्राफ हैमिल्टनियन चक्र है अगर और केवल अगर यह द्विसंबद्ध है; इस मामले में, बाहरी चेहरा अद्वितीय हैमिल्टनियन चक्र बनाता है।[5] अधिक आम तौर पर, एक बाहरी प्लैनर ग्राफ में सबसे लंबे चक्र का आकार इसके सबसे बड़े द्विसंबद्ध घटक में शीर्षों की संख्या के समान होता है। इस कारण से हेमिल्टनियन चक्रों और बाह्यप्लानर ग्राफों में सबसे लंबे चक्रों को रैखिक समय में हल किया जा सकता है, आर्बिट्रेरी ग्राफों के लिए इन समस्याओं की एनपी-पूर्णता के विपरीत।
प्रत्येक अधिक से अधिक बाहरी ग्राफ़ हैमिल्टनिकता की तुलना में एक मजबूत स्थिति को संतुष्ट करता है: यह नोड पैनसाइक्लिक ग्राफ है, जिसका अर्थ है कि प्रत्येक शीर्ष v और प्रत्येक k के लिए ग्राफ में तीन से लेकर शीर्षों की संख्या तक, एक लंबाई-k चक्र होता है जिसमें v होता है। इस लंबाई का एक चक्र एक त्रिभुज को बार-बार हटाकर पाया जा सकता है जो शेष ग्राफ़ से एक किनारे से जुड़ा हुआ है, जैसे कि हटाया गया शीर्ष v नहीं है, जब तक कि शेष ग्राफ़ के बाहरी फलक की लंबाई k न हो।[6]
एक प्लानर ग्राफ आउटरप्लानर है अगर और केवल अगर इसके प्रत्येक बायकनेक्टेड घटक आउटरप्लानर हैं।[4]
रंग
सभी लूपलेस आउटरप्लानर ग्राफ़ को केवल तीन रंगों का उपयोग करके रंगीन किया जा सकता है;[7] यह तथ्य फिस्क (1978) द्वारा च्वाटल की आर्ट गैलरी प्रमेय के सरलीकृत प्रमाण में प्रमुखता से दिखाया गया है। एक लालची रंग एल्गोरिदम द्वारा रैखिक समय में एक 3-रंग पाया जा सकता है जो अधिकतम डिग्री (ग्राफ सिद्धांत) के किसी भी शीर्ष को हटा देता है, शेष ग्राफ को पुनरावर्ती रूप से रंग देता है, और फिर हटाए गए शीर्ष को अपने दो पड़ोसियों के रंगों से अलग रंग के साथ वापस जोड़ता है।
वाइज़िंग के प्रमेय के अनुसार, किसी भी ग्राफ का रंगीन सूचकांक (किनारों को रंगने के लिए आवश्यक रंगों की न्यूनतम संख्या ताकि दो आसन्न किनारों का एक ही रंग न हो) या तो ग्राफ के किसी भी शीर्ष की अधिकतम डिग्री (ग्राफ सिद्धांत) या एक प्लस अधिकतम डिग्री है। हालांकि, कनेक्टेड आउटरप्लानर ग्राफ में, रंगीन सूचकांक अधिकतम डिग्री के बराबर होता है, सिवाय इसके कि जब ग्राफ विषम लंबाई का चक्र (ग्राफ सिद्धांत) बनाता है।[8] रंगों की इष्टतम संख्या के साथ किनारे का रंग कमजोर दोहरे पेड़ के चौड़ाई-प्रथम ट्रैवर्सल के आधार पर रैखिक समय में पाया जा सकता है।[7]
अन्य गुण
आउटरप्लानर ग्राफ़ में अध: पतन (ग्राफ़ सिद्धांत) अधिकतम दो में होता है: एक आउटरप्लानर ग्राफ के प्रत्येक सबग्राफ में अधिकतम दो डिग्री के साथ एक वर्टेक्स होता है।[9] आउटरप्लानर ग्राफ़ में अधिकतम दो पर ट्रेविड्थ होता है, जिसका अर्थ है कि कई ग्राफ़ ऑप्टिमाइज़ेशन समस्याएँ जो एनपी-पूर्ण ग्राफ़ के लिए होती हैं, बहुपद समय में गतिशील प्रोग्रामिंग द्वारा हल की जा सकती हैं जब इनपुट आउटरप्लानर होता है। आमतौर पर, के-आउटरप्लानर ग्राफ़ में ट्रेविड्थ ओ (के) होता है।[10]
प्रत्येक बाहरीप्लानर ग्राफ को विमान में अक्ष-संरेखित आयतों के प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है, इसलिए बाहरीप्लानर ग्राफ में बॉक्सिसिटी अधिकतम दो होती है।[11]
रेखांकन के संबंधित परिवार
हर आउटरप्लानर ग्राफ एक प्लेनर ग्राफ है। प्रत्येक आउटरप्लानर ग्राफ भी एक श्रृंखला-समानांतर ग्राफ का एक सबग्राफ है।[12] हालाँकि, सभी प्लानर श्रृंखला-समानांतर ग्राफ़ आउटरप्लानर नहीं हैं। पूर्ण द्विदलीय ग्राफ K2,3 प्लानर और श्रृंखला-समानांतर है लेकिन आउटरप्लानर नहीं है। दूसरी ओर, पूरा ग्राफ K4 प्लानर है लेकिन न तो श्रृंखला-समानांतर है और न ही आउटरप्लानर है। हर वृक्ष (ग्राफ थ्योरी) और हर कैक्टस का ग्राफ आउटरप्लानर है।[13]
एक एम्बेडेड आउटरप्लानर ग्राफ का तलीय दोहरी ग्राफ (वह ग्राफ जिसमें एम्बेडिंग के प्रत्येक बंधे हुए चेहरे के लिए एक शीर्ष है, और आसन्न बंधे चेहरों की हर जोड़ी के लिए एक किनारा है) एक जंगल है, और एक हालीन ग्राफ का कमजोर प्लानर डुअल एक है आउटरप्लानर ग्राफ। एक प्लानर ग्राफ आउटरप्लानर है अगर और केवल अगर इसकी कमजोर दोहरी एक जंगल है, और यह हैलिन है अगर और केवल अगर इसकी कमजोर दोहरी बाइकनेक्टेड और आउटरप्लानर है।[14] आउटरप्लानरिटी की डिग्री की धारणा है। एक ग्राफ़ का 1-आउटरप्लानर एम्बेडिंग एक आउटरप्लानर एम्बेडिंग के समान है। k > 1 के लिए एक प्लानर एम्बेडिंग को K-आउटरप्लानर ग्राफ|k-आउटरप्लानर कहा जाता है यदि बाहरी फलक पर वर्टिकल को हटाने से (k − 1)-आउटरप्लानर एम्बेडिंग होता है। एक ग्राफ के-आउटरप्लानर है यदि इसमें के-आउटरप्लानर एम्बेडिंग है।[15] एक 1-प्लानर ग्राफ़#सामान्यीकरण और संबंधित अवधारणाएं|बाहरी-1-प्लानर ग्राफ़, 1-प्लानर ग्राफ़ के समान रूप से, डिस्क की सीमा पर शीर्षों के साथ, और प्रति किनारे अधिकतम एक क्रॉसिंग के साथ डिस्क में खींचा जा सकता है।
प्रत्येक अधिक से अधिक बाह्यप्लानर ग्राफ एक तारकीय ग्राफ है। प्रत्येक अधिकतम बाह्यप्लानर ग्राफ एक साधारण बहुभुज का दृश्यता ग्राफ है।[16] मैक्सिमल आउटरप्लानर ग्राफ़ भी बहुभुज त्रिभुजों के ग्राफ़ के रूप में बनते हैं। वे k-वृक्ष | 2-ट्रीज़, सीरीज़-पैरेलल ग्राफ़ और कॉर्डल ग्राफ़ के उदाहरण हैं।
हर आउटरप्लानर ग्राफ एक सर्कल ग्राफ है, एक सर्कल के कॉर्ड्स के सेट का इंटरसेक्शन ग्राफ।[17]
टिप्पणियाँ
- ↑ 1.0 1.1 Felsner (2004).
- ↑ Chartrand & Harary (1967); Sysło (1979); Brandstädt, Le & Spinrad (1999), Proposition 7.3.1, p. 117; Felsner (2004).
- ↑ Diestel (2000).
- ↑ 4.0 4.1 Sysło (1979).
- ↑ Chartrand & Harary (1967); Sysło (1979).
- ↑ Li, Corneil & Mendelsohn (2000), Proposition 2.5.
- ↑ 7.0 7.1 Proskurowski & Sysło (1986).
- ↑ Fiorini (1975).
- ↑ Lick & White (1970).
- ↑ Baker (1994).
- ↑ Scheinerman (1984); Brandstädt, Le & Spinrad (1999), p. 54.
- ↑ Brandstädt, Le & Spinrad (1999), p. 174.
- ↑ Brandstädt, Le & Spinrad (1999), p. 169.
- ↑ Sysło & Proskurowski (1983).
- ↑ Kane & Basu (1976); Sysło (1979).
- ↑ El-Gindy (1985); Lin & Skiena (1995); Brandstädt, Le & Spinrad (1999), Theorem 4.10.3, p. 65.
- ↑ Wessel & Pöschel (1985); Unger (1988).
संदर्भ
- Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "The problem of outer embeddings in pseudosurfaces", Ars Combinatoria, 71: 79–91.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2004), "Obstruction sets for outer-bananas-surface graphs", Ars Combinatoria, 73: 65–77.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2006), "Uncountable graphs with all their vertices in one face", Acta Mathematica Hungarica, 112 (4): 307–313, doi:10.1007/s10474-006-0082-0, S2CID 123241658.
- Boza, Luis; Fedriani, Eugenio M.; Núñez, Juan (2010), "Outer-embeddability in certain pseudosurfaces arising from three spheres", Discrete Mathematics, 310 (23): 3359–3367, doi:10.1016/j.disc.2010.07.027.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, Society for Industrial and Applied Mathematics, ISBN 0-89871-432-X.
- Chartrand, Gary; Harary, Frank (1967), "Planar permutation graphs", Annales de l'Institut Henri Poincaré B, 3 (4): 433–438, MR 0227041.
- Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, p. 107, ISBN 0-387-98976-5.
- El-Gindy, H. (1985), Hierarchical decomposition of polygons with applications, Ph.D. thesis, McGill University. As cited by Brandstädt, Le & Spinrad (1999).
- Felsner, Stefan (2004), Geometric graphs and arrangements: some chapters from combinational geometry, Vieweg+Teubner Verlag, p. 6, ISBN 978-3-528-06972-8.
- Fiorini, Stanley (1975), "On the chromatic index of outerplanar graphs", Journal of Combinatorial Theory, Series B, 18 (1): 35–38, doi:10.1016/0095-8956(75)90060-X.
- Fisk, Steve (1978), "A short proof of Chvátal's watchman theorem", Journal of Combinatorial Theory, Series B, 24 (3): 374, doi:10.1016/0095-8956(78)90059-X.
- Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society, 38: 215–219, MR 0389672.
- Kane, Vinay G.; Basu, Sanat K. (1976), "On the depth of a planar graph", Discrete Mathematics, 14 (1): 63–67, doi:10.1016/0012-365X(76)90006-6.
- Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics, 98 (3): 219–225, doi:10.1016/S0166-218X(99)00163-8.
- Lick, Don R.; White, Arthur T. (1970), "k[[Category: Templates Vigyan Ready]]-degenerate graphs", Canadian Journal of Mathematics, 22 (5): 1082–1096, doi:10.4153/CJM-1970-125-1
{{citation}}: URL–wikilink conflict (help). - Lin, Yaw-Ling; Skiena, Steven S. (1995), "Complexity aspects of visibility graphs", International Journal of Computational Geometry and Applications, 5 (3): 289–312, doi:10.1142/S0218195995000179.
- Proskurowski, Andrzej; Sysło, Maciej M. (1986), "Efficient vertex-and edge-coloring of outerplanar graphs", SIAM Journal on Algebraic and Discrete Methods, 7: 131–136, doi:10.1137/0607016.
- Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters of a Graph, Ph.D. thesis, Princeton University. As cited by Brandstädt, Le & Spinrad (1999).
- Sysło, Maciej M. (1979), "Characterizations of outerplanar graphs", Discrete Mathematics, 26 (1): 47–53, doi:10.1016/0012-365X(79)90060-8.
- Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, vol. 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
- Unger, Walter (1988), "On the k-colouring of circle-graphs", Proc. 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832.
- Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, vol. 73, B.G. Teubner, pp. 207–210. As cited by Unger (1988).
