कैक्टस ग्राफ
ग्राफ सिद्धांत में, एक कैक्टस (कभी-कभी कैक्टस ट्री कहा जाता है) एक जुड़ा हुआ ग्राफ होता है जिसमें किसी भी दो सरल चक्रों (ग्राफ सिद्धांत) में अधिकतम एक शीर्ष (ग्राफ सिद्धांत) सामान्य होता है। समतुल्य रूप से, यह एक जुड़ा हुआ ग्राफ है जिसमें प्रत्येक किनारा अधिक से अधिक एक साधारण चक्र से संबंधित होता है, या (असतहीय कैक्टस के लिए) जिसमें प्रत्येक ब्लॉक (कट-वर्टेक्स के बिना अधिकतम सबग्राफ) एक किनारा या एक चक्र होता है।
गुण
कैक्टि आउटरप्लानर ग्राफ हैं। हर स्यूडोफ़ॉरेस्ट एक कैक्टस है। एक असतहीय ग्राफ एक कैक्टस है यदि और केवल यदि प्रत्येक ब्लॉक (यह ग्राफ थ्योरी की शब्दावली है।) या तो एक सरल चक्र (ग्राफ सिद्धांत) या एक किनारा है।
ग्राफ़ का परिवार जिसमें प्रत्येक घटक (ग्राफ़ सिद्धांत) एक कैक्टस होता है, ग्राफ़ लघु संचालन के तहत नीचे की ओर बंद होता है। इस ग्राफ़ परिवार को एक एकल फॉरबिडेन माइनर द्वारा चित्रित किया जा सकता है, पूर्ण ग्राफ़ K4 से एक किनारे को हटाकर चार शीर्ष हीरा ग्राफ़ बनाया गया है।[1]
त्रिकोणीय कैक्टस
एक त्रिकोणीय कैक्टस एक विशेष प्रकार का कैक्टस ग्राफ है जैसे कि प्रत्येक चक्र की लंबाई तीन होती है और प्रत्येक किनारा एक चक्र से संबंधित होता है। उदाहरण के लिए, मित्रता रेखांकन, त्रिभुजों के संग्रह से बने रेखांकन एक ही साझा शीर्ष पर एक साथ जुड़ते हैं, त्रिकोणीय कैक्टि होते हैं। कैक्टस ग्राफ़ होने के साथ-साथ त्रिकोणीय कैक्टि ब्लॉक ग्राफ और स्थानीय रेखीय ग्राफ़ भी हैं।
त्रिकोणीय कैक्टस में यह गुण होता है कि यदि कोई मिलान (ग्राफ सिद्धांत) हटा दिया जाता है तो भी वे जुड़े रहते हैं; दिए गए शीर्षों की संख्या के लिए, उनके पास इस गुण के साथ सबसे कम संभव किनारे होते हैं। कोने की एक विषम संख्या वाले प्रत्येक पेड़ को एक त्रिकोणीय कैक्टस में किनारों को जोड़कर बढ़ाया जा सकता है, जो एक मिलान को हटाने के पश्चात जुड़े रहने के गुण के साथ न्यूनतम वृद्धि प्रदान करता है।[2]
किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ प्लेनर ग्राफ हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण (ग्राफ़ थ्योरी के गणितीय क्षेत्र ) में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का सन्निकटन अनुपात 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।[3]
सबसे बड़े त्रिकोणीय कैक्टस को खोजने के लिए एल्गोरिदम लोवाज़ और प्लमर के प्रमेय से जुड़ा हुआ है जो इस सबसे बड़े कैक्टस में त्रिकोणों की संख्या को दर्शाता है।[4]
लोवाज़ और प्लमर दिए गए ग्राफ़ के कोने और किनारों के विभाजन के जोड़े को उपसमुच्चय में मानते हैं, गुण के साथ ग्राफ के प्रत्येक त्रिकोण में शीर्ष विभाजन के एक वर्ग में दो कोने हैं या किनारे विभाजन के एक वर्ग में सभी तीन किनारे हैं; वे इस गुण के साथ विभाजन की एक जोड़ी को वैध कहते हैं।
फिर सबसे बड़े त्रिकोणीय कैक्टस में त्रिकोणों की संख्या अधिकतम, वैध विभाजनों के जोड़े के बराबर होती है और , का
- ,
जहां दिए गए ग्राफ में शीर्षों की संख्या है और एज वर्गों द्वारा मिले शीर्ष वर्गों की संख्या है .
हाल ही में, एक तंग चरम सीमा सिद्ध हुई थी[5] जिसने दिखाया कि किसी भी समतल ग्राफ को दिया गया , में हमेशा एक कैक्टस सबग्राफ उपस्थित होता है जिसमें कम से कम युक्त के त्रिकोणीय फलको का अंश है। यह परिणाम उपरोक्त न्यूनतम-अधिकतम सूत्र का उपयोग किए बिना अधिकतम प्लानर सबग्राफ समस्या के लिए 4/9 - सन्निकटन एल्गोरिथ्म का प्रत्यक्ष विश्लेषण दर्शाता है।
रोजा का अनुमान
त्रिकोणीय कैक्टस से संबंधित एक महत्वपूर्ण अनुमान रोजा का अनुमान है, जिसका नाम अलेक्जेंडर रोजा के नाम पर रखा गया है, जो कहता है कि सभी त्रिकोणीय कैक्टि सुन्दर या लगभग सुन्दर हैं।[6] ज्यादा ठीक
टी ≡ 0, 1 मॉड 4 ब्लॉक वाले सभी त्रिकोणीय कैक्टि सुन्दर हैं, और टी ≡ 2, 3 मॉड 4 वाले सुन्दर हैं।
एल्गोरिदम और अनुप्रयोग
कुछ सुविधा स्थान की समस्याएं (एफएलपी) जो सामान्य ग्राफ़ के लिए एनपी कठिन हैं, साथ ही कुछ अन्य ग्राफ़ समस्याएं कैक्टि के लिए बहुपद समय फलन (कंप्यूटर विज्ञान में, समय जटिलता) में हल की जा सकती हैं।[7][8]
चूंकि कैक्टि बाहरी प्लैनर ग्राफ के विशेष मामले हैं, बहुपद समय में ग्राफ पर कई संयोजी अनुकूलन समस्याओं को उनके लिए हल किया जा सकता है।[9]
कैक्टि विद्युत सर्किट का प्रतिनिधित्व करता है जिसमें उपयोगी गुण होते हैं। कैक्टि का एक प्रारंभिक अनुप्रयोग ऑप-एम्प्स के प्रतिनिधित्व से जुड़ा था।[10][11][12]
विभिन्न जीनोम या जीनोम के कुछ हिस्सों के बीच संबंधों का प्रतिनिधित्व करने के उपायो के रूप में कैक्टि का उपयोग तुलनात्मक जीनोमिक्स में भी किया गया है।[13]
यदि एक कैक्टस जुड़ा हुआ है, और इसका प्रत्येक शीर्ष अधिकतम दो ब्लॉकों से संबंधित है, तो इसे क्रिसमस कैक्टस कहा जाता है। प्रत्येक बहुफलकीय ग्राफ में एक क्रिसमस कैक्टस सबग्राफ होता है जिसमें इसके सभी कोने सम्मलित होते हैं, एक ऐसा तथ्य जो लीटन और & मोइत्रा (2010) द्वारा एक प्रमाण में एक आवश्यक भूमिका निभाता है कि हर बहुफलकीय ग्राफ में यूक्लिडियन विमान में एक भौगोलिक रूटिंग है, शीर्षों के लिए निर्देशांकों का एक कार्य जिसके लिए भौगोलिक रूटिंग शीर्षों के सभी युग्मों के बीच संदेशों को मार्ग करने में सफल होता है।[14]
टोपोलॉजिकल ग्राफ सिद्धांत में, वे ग्राफ़ जिनके सेलुलर एम्बेडिंग सभी प्लैनर ग्राफ़ हैं, कैक्टस ग्राफ़ के उपपरिवार हैं, अतिरिक्त गुणधर्म के साथ जो कि प्रत्येक शीर्ष अधिकतम एक चक्र से संबंधित है। इन ग्राफ़ में दो वर्जित अवयस्क, डायमंड ग्राफ़ और पांच शीर्ष फ्रेंडशिप ग्राफ़ हैं।[15]
इतिहास
कोडी हुसिमी द्वारा इन रेखांकन पर पिछले काम के सम्मान में फ्रैंक हैरिस और जॉर्ज यूजीन उहलेनबेक द्वारा उन्हें दिए गए हुसिमी पेड़ों के नाम के तहत पहली बार कैक्टी का अध्ययन किया गया था।[16][17] वही हरारी-उहलेनबेक पेपर इस प्रकार के ग्राफ़ के लिए "कैक्टस" नाम रखता है जिसमें प्रत्येक चक्र एक त्रिकोण है, लेकिन अब सभी लंबाई के चक्रों की अनुमति देना मानक है।
इस बीच, हुसिमी पेड़ का नाम सामान्यतः उन ग्राफ़ों को संदर्भित करने के लिए आया था जिनमें प्रत्येक ब्लॉक (यह ग्राफ थ्योरी की शब्दावली) एक पूर्ण ग्राफ़ है (समतुल्य रूप से, किसी अन्य ग्राफ़ में ब्लॉक के प्रतिच्छेदन ग्राफ़)। इस प्रयोग का हुसिमी के काम से बहुत कम लेना-देना था, और अधिक प्रासंगिक शब्द ब्लॉक ग्राफ अब इस परिवार के लिए उपयोग किया जाता है; चूंकि, इस अस्पष्टता के कारण यह वाक्यांश कैक्टस ग्राफ़ को संदर्भित करने के लिए बहुत कम उपयोग किया जाता है।[18]
संदर्भ
- ↑ El-Mallah, Ehab; Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems, 35 (3): 354–362, doi:10.1109/31.1748
- ↑ Farley, Arthur M.; Proskurowski, Andrzej (1982), "Networks immune to isolated line failures", Networks, 12 (4): 393–403, doi:10.1002/net.3230120404, MR 0686540
- ↑ Călinescu, Gruia; Fernandes, Cristina G; Finkler, Ulrich; Karloff, Howard (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms, 2, 27 (2): 269–302, CiteSeerX 10.1.1.47.4731, doi:10.1006/jagm.1997.0920, S2CID 8329680
- ↑ Lovász, L.; Plummer, M.D. (2009), Matching Theory, AMS Chelsea Publishing Series, ISBN 9780821847596
- ↑ Chalermsook, Parinya; Schmid, Andreas; Uniyal, Sumedha (2019), "A tight extremal bound on the Lovász cactus number in planar graphs", in Niedermeier, Rolf; Paul, Christophe (eds.), 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, LIPIcs, vol. 126, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 19:1–19:14, arXiv:1804.03485, doi:10.4230/LIPIcs.STACS.2019.19
- ↑ Rosa, A. (1988), "Cyclic Steiner Triple Systems and Labelings of Triangular Cacti", Scientia, 1: 87–95.
- ↑ Ben-Moshe, Boaz; Bhattacharya, Binay; Shi, Qiaosheng (2005), "Efficient algorithms for the weighted 2-center problem in a cactus graph", Algorithms and Computation, 16th Int. Symp., ISAAC 2005, Lecture Notes in Computer Science, vol. 3827, Springer-Verlag, pp. 693–703, doi:10.1007/11602613_70, ISBN 978-3-540-30935-2
- ↑ Zmazek, Blaz; Zerovnik, Janez (2005), "Estimating the traffic on weighted cactus networks in linear time", Ninth International Conference on Information Visualisation (IV'05), pp. 536–541, doi:10.1109/IV.2005.48, ISBN 978-0-7695-2397-2, S2CID 15963409
- ↑ Korneyenko, N. M. (1994), "Combinatorial algorithms on a class of graphs", Discrete Applied Mathematics, 54 (2–3): 215–217, doi:10.1016/0166-218X(94)90022-1. Translated from Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci., (1984) no. 3, pp. 109-111 (in Russian)
- ↑ Nishi, Tetsuo; Chua, Leon O. (1986), "Topological proof of the Nielsen-Willson theorem", IEEE Transactions on Circuits and Systems, 33 (4): 398–405, doi:10.1109/TCS.1986.1085935
- ↑ Nishi, Tetsuo; Chua, Leon O. (1986), "Uniqueness of solution for nonlinear resistive circuits containing CCCS's or VCVS's whose controlling coefficients are finite", IEEE Transactions on Circuits and Systems, 33 (4): 381–397, doi:10.1109/TCS.1986.1085934
- ↑ Nishi, Tetsuo (1991), "On the number of solutions of a class of nonlinear resistive circuit", Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore, pp. 766–769
- ↑ Paten, Benedict; Diekhans, Mark; Earl, Dent; St. John, John; Ma, Jian; Suh, Bernard; Haussler, David (2010), "Cactus Graphs for Genome Comparisons", Research in Computational Molecular Biology, Lecture Notes in Computer Science, vol. 6044, pp. 410–425, doi:10.1007/978-3-642-12683-3_27, ISBN 978-3-642-12682-6
- ↑ Leighton, Tom; Moitra, Ankur (2010), "Some Results on Greedy Embeddings in Metric Spaces" (PDF), Discrete & Computational Geometry, 44 (3): 686–705, doi:10.1007/s00454-009-9227-6, S2CID 11186402.
- ↑ Nordhaus, E. A.; Ringeisen, R. D.; Stewart, B. M.; White, A. T. (1972), "A Kuratowski-type theorem for the maximum genus of a graph", Journal of Combinatorial Theory, Series B, 12 (3): 260–267, doi:10.1016/0095-8956(72)90040-8, MR 0299523
- ↑ Harary, Frank; Uhlenbeck, George E. (1953), "On the number of Husimi trees, I", Proceedings of the National Academy of Sciences, 39 (4): 315–322, Bibcode:1953PNAS...39..315H, doi:10.1073/pnas.39.4.315, MR 0053893, PMC 1063779, PMID 16589268
- ↑ Husimi, Kodi (1950), "Note on Mayers' theory of cluster integrals", Journal of Chemical Physics, 18 (5): 682–684, Bibcode:1950JChPh..18..682H, doi:10.1063/1.1747725, MR 0038903
- ↑ See, e.g., MR0659742, a 1983 review by Robert E. Jamison of a paper using the other definition, which attributes the ambiguity to an error in a book by Mehdi Behzad and Gary Chartrand.
