View source for कैक्टस ग्राफ

{{short description|Mathematical tree of cycles}}
[[Image:Cactus graph.svg|thumb|225px|कैक्टस ग्राफ]][[ग्राफ सिद्धांत]] में, एक कैक्टस (कभी-कभी कैक्टस ट्री कहा जाता है) एक [[जुड़ा हुआ ग्राफ]] होता है जिसमें किसी भी दो सरल [[चक्र (ग्राफ सिद्धांत)|चक्रों (ग्राफ सिद्धांत)]] में अधिकतम एक [[शीर्ष (ग्राफ सिद्धांत)]] सामान्य होता है। समतुल्य रूप से, यह एक जुड़ा हुआ ग्राफ है जिसमें प्रत्येक किनारा अधिक से अधिक एक साधारण चक्र से संबंधित होता है, या (असतहीय कैक्टस के लिए) जिसमें प्रत्येक ब्लॉक ([[कट-वर्टेक्स]] के बिना अधिकतम सबग्राफ) एक किनारा या एक चक्र होता है।

== गुण ==
कैक्टि [[आउटरप्लानर ग्राफ]] हैं। हर [[ seudoforest ]] एक कैक्टस है। एक गैर-तुच्छ ग्राफ एक कैक्टस है अगर और केवल अगर ग्राफ सिद्धांत की हर शब्दावली # ब्लॉक या तो एक चक्र (ग्राफ सिद्धांत) या एक किनारा है।

ग्राफ़ का परिवार जिसमें प्रत्येक घटक (ग्राफ़ सिद्धांत) एक कैक्टस है, ग्राफ़ लघु संचालन के तहत [[नीचे की ओर बंद]] है। इस ग्राफ़ परिवार को एक एकल वर्जित माइनर द्वारा चित्रित किया जा सकता है, पूर्ण ग्राफ़ K से एक किनारे को हटाकर चार-शीर्ष हीरे का ग्राफ़ बनाया गया है<sub>4</sub>.<ref>{{citation |last1=El-Mallah |first1=Ehab |last2=Colbourn |first2=Charles J. |author2-link=Charles Colbourn |title=The complexity of some edge deletion problems |journal=IEEE Transactions on Circuits and Systems |volume=35 |issue=3 |year=1988 |pages=354–362 |doi=10.1109/31.1748}}</ref>


== त्रिकोणीय कैक्टस ==
[[File:Friendship graphs.svg|thumb|upright=1.6|मैत्री ग्राफ त्रिकोणीय कैक्टि हैं]]एक त्रिकोणीय कैक्टस एक विशेष प्रकार का कैक्टस ग्राफ है जैसे कि प्रत्येक चक्र की लंबाई तीन होती है और प्रत्येक किनारा एक चक्र से संबंधित होता है। उदाहरण के लिए, मित्रता रेखांकन, त्रिभुजों के संग्रह से बने रेखांकन एक ही साझा शीर्ष पर एक साथ जुड़ते हैं, त्रिकोणीय कैक्टि होते हैं। कैक्टस ग्राफ़ होने के साथ-साथ त्रिकोणीय कैक्टि [[ब्लॉक ग्राफ]]़ और स्थानीय रेखीय ग्राफ़ भी हैं।

त्रिकोणीय कैक्टस में यह गुण होता है कि यदि कोई [[मिलान (ग्राफ सिद्धांत)]] उनसे हटा दिया जाए तो वे जुड़े रहते हैं; दिए गए शीर्षों की संख्या के लिए, उनके पास इस गुण के साथ सबसे कम संभव किनारे होते हैं। विषम संख्या में कोने वाले प्रत्येक पेड़ को किनारों को जोड़कर त्रिकोणीय कैक्टस में बढ़ाया जा सकता है,
एक मिलान को हटाने के बाद जुड़े रहने की संपत्ति के साथ न्यूनतम वृद्धि देना।<ref>{{citation
 | last1 = Farley | first1 = Arthur M.
 | last2 = Proskurowski | first2 = Andrzej
 | doi = 10.1002/net.3230120404
 | issue = 4
 | journal = Networks
 | mr = 686540
 | pages = 393–403
 | title = Networks immune to isolated line failures
 | volume = 12
 | year = 1982}}</ref>
किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ [[प्लेनर ग्राफ]]़ हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का [[सन्निकटन अनुपात]] 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।<ref>{{citation
 | last1 = Călinescu | first1 = Gruia
 | last2 = Fernandes | first2 = Cristina G
 | last3 = Finkler | first3 = Ulrich
 | last4 = Karloff | first4 = Howard
 | doi = 10.1006/jagm.1997.0920
 | journal = Journal of Algorithms
 | pages = 269–302
 | series = 2
 | title = A Better Approximation Algorithm for Finding Planar Subgraphs
 | volume = 27
 | issue = 2
 | year = 2002| citeseerx = 10.1.1.47.4731
 | s2cid = 8329680
 }}</ref>
सबसे बड़े त्रिकोणीय कैक्टस को खोजने के लिए एल्गोरिदम लोवाज़ और प्लमर के प्रमेय से जुड़ा हुआ है जो इस सबसे बड़े कैक्टस में त्रिकोणों की संख्या को दर्शाता है।<ref>{{Citation|last1=Lovász|first1=L.|author1-link=László_Lovász|last2= Plummer |first2=M.D.|author-link2=Michael_D._Plummer|date=2009|title=Matching Theory|publisher=AMS Chelsea Publishing Series|isbn= 9780821847596}}</ref>
लोवाज़ और प्लमर दिए गए ग्राफ़ के कोने और किनारों के विभाजन के जोड़े को उपसमुच्चय में मानते हैं, संपत्ति के साथ कि ग्राफ के प्रत्येक त्रिकोण में या तो शीर्ष विभाजन के एक वर्ग में दो कोने होते हैं या सभी तीन किनारे एक ही वर्ग में होते हैं। किनारा विभाजन; वे इस संपत्ति के साथ विभाजन की एक जोड़ी को वैध कहते हैं।
फिर सबसे बड़े त्रिकोणीय कैक्टस में त्रिकोणों की संख्या अधिकतम, वैध विभाजनों के जोड़े के बराबर होती है <math>\mathcal{P}=\{V_1, V_2, \dots, V_k\}</math> और <math>\mathcal{Q} = \{E_1, E_2, \dots, E_m\}</math>, का
:<math>\sum_{i=1}^{m}\frac{(u_i - 1)}{2} + n - k,</math>,
कहाँ <math>n</math> दिए गए ग्राफ में शीर्षों की संख्या है और <math>u_i</math> एज क्लास द्वारा मिले वर्टेक्स क्लास की संख्या है <math>E_i</math>.

हाल ही में, एक तंग चरम सीमा सिद्ध हुई थी<ref>{{citation
 | last1 = Chalermsook | first1 = Parinya
 | last2 = Schmid | first2 = Andreas
 | last3 = Uniyal | first3 = Sumedha
 | editor1-last = Niedermeier | editor1-first = Rolf
 | editor2-last = Paul | editor2-first = Christophe
 | arxiv = 1804.03485
 | contribution = A tight extremal bound on the Lovász cactus number in planar graphs
 | doi = 10.4230/LIPIcs.STACS.2019.19
 | pages = 19:1–19:14
 | publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik
 | series = LIPIcs
 | title = 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany
 | volume = 126
 | year = 2019}}</ref> जिसने दिखाया कि किसी भी [[समतल ग्राफ]] को दिया गया है <math>G</math>, हमेशा एक कैक्टस सबग्राफ मौजूद होता है <math>C \subseteq G</math> कम से कम युक्त <math>1/6</math> के त्रिकोणीय चेहरों का अंश <math>G</math>. यह परिणाम उपरोक्त न्यूनतम-अधिकतम सूत्र का उपयोग किए बिना अधिकतम प्लानर सबग्राफ समस्या के लिए 4/9 - सन्निकटन एल्गोरिथ्म का प्रत्यक्ष विश्लेषण दर्शाता है।

=== रोजा का अनुमान ===

त्रिकोणीय कैक्टस से संबंधित एक महत्वपूर्ण अनुमान है रोजा का अनुमान, जिसका नाम अलेक्जेंडर रोजा के नाम पर रखा गया है, जो कहता है कि सभी त्रिकोणीय कैक्टि ग्रेसफुल_लेबलिंग या लगभग-सुशोभित हैं।<ref name="Rosa1988">{{citation|last=Rosa|first=A.|title=Cyclic Steiner Triple Systems and Labelings of Triangular Cacti|journal=Scientia|volume=1|pages=87–95|year=1988}}.</ref> ज्यादा ठीक

टी ≡ 0, 1 मॉड 4 ब्लॉक वाले सभी त्रिकोणीय कैक्टि ग्रेसफुल हैं, और टी ≡ 2, 3 मॉड 4 वाले ग्रेसफुल हैं।

== एल्गोरिदम और अनुप्रयोग ==
कुछ सुविधा स्थान समस्याएं जो सामान्य ग्राफ़ के लिए [[ एनपी कठिन ]] हैं, साथ ही कुछ अन्य ग्राफ़ समस्याएं कैक्टि के लिए बहुपद समय में हल की जा सकती हैं।<ref>{{citation |first1=Boaz |last1=Ben-Moshe |first2=Binay |last2=Bhattacharya |first3=Qiaosheng |last3=Shi |year=2005 |contribution=Efficient algorithms for the weighted 2-center problem in a cactus graph  |publisher=Springer-Verlag |series=[[Lecture Notes in Computer Science]] |volume=3827 |pages=693–703 |title=Algorithms and Computation, 16th Int. Symp., ISAAC 2005| doi=10.1007/11602613_70|isbn=978-3-540-30935-2 }}</ref><ref>{{citation |first1=Blaz |last1=Zmazek |first2=Janez |last2=Zerovnik |year=2005 |pages=536–541 |doi=10.1109/IV.2005.48 |contribution=Estimating the traffic on weighted cactus networks in linear time |title=Ninth International Conference on Information Visualisation (IV'05) |isbn=978-0-7695-2397-2|s2cid=15963409 }}</ref>
चूंकि कैक्टि बाहरी प्लैनर ग्राफ के विशेष मामले हैं, बहुपद समय में ग्राफ पर कई संयोजी अनुकूलन समस्याओं को उनके लिए हल किया जा सकता है।<ref>{{Citation |author=Korneyenko, N. M. |title=Combinatorial algorithms on a class of graphs |journal=Discrete Applied Mathematics|volume=54 |issue=2–3 |pages=215–217 |year=1994 |doi=10.1016/0166-218X(94)90022-1 |postscript=.|doi-access=free }} Translated from ''Notices of the BSSR Academy of Sciences, Ser. Phys.-Math. Sci.'', (1984) no. 3, pp. 109-111 {{in lang|ru}}</ref>
कैक्टि [[विद्युत सर्किट]] का प्रतिनिधित्व करता है जिसमें उपयोगी गुण होते हैं। कैक्टि का एक प्रारंभिक अनुप्रयोग ऑप-एम्प्स के प्रतिनिधित्व से जुड़ा था।<ref>{{citation |first1=Tetsuo |last1=Nishi |first2=Leon O. |last2=Chua |author2-link=Leon O. Chua |title=Topological proof of the Nielsen-Willson theorem |journal=IEEE Transactions on Circuits and Systems |volume=33 |issue=4 |pages=398–405 |year=1986 |doi=10.1109/TCS.1986.1085935}}</ref><ref>{{citation |first1=Tetsuo |last1=Nishi |first2=Leon O. |last2=Chua |author2-link=Leon O. Chua |title=Uniqueness of solution for nonlinear resistive circuits containing CCCS's or VCVS's whose controlling coefficients are finite |journal=IEEE Transactions on Circuits and Systems |volume=33 |issue=4 |pages=381–397 |year=1986 |doi=10.1109/TCS.1986.1085934}}</ref><ref>{{citation |first=Tetsuo |last=Nishi |contribution=On the number of solutions of a class of nonlinear resistive circuit |title=Proceedings of the IEEE International Symposium on Circuits and Systems, Singapore |pages=766–769 |year=1991}}</ref>
विभिन्न जीनोम या जीनोम के कुछ हिस्सों के बीच संबंधों का प्रतिनिधित्व करने के तरीके के रूप में कैक्टि का उपयोग [[तुलनात्मक जीनोमिक्स]] में भी किया गया है।<ref>{{citation |first1=Benedict |last1=Paten |first2=Mark |last2=Diekhans |first3=Dent |last3=Earl |first4=John |last4=St. John |first5=Jian |last5=Ma |first6=Bernard |last6=Suh |first7=David |last7=Haussler |title=Research in Computational Molecular Biology |volume=6044 |pages=[https://archive.org/details/researchincomput0000reco/page/410 410–425] |year=2010 |doi=10.1007/978-3-642-12683-3_27 |chapter=Cactus Graphs for Genome Comparisons |series=Lecture Notes in Computer Science |isbn=978-3-642-12682-6 |chapter-url-access=registration |chapter-url=https://archive.org/details/researchincomput0000reco/page/410 }}</ref>
यदि एक कैक्टस जुड़ा हुआ है, और इसका प्रत्येक शीर्ष अधिकतम दो ब्लॉकों से संबंधित है, तो इसे क्रिसमस कैक्टस कहा जाता है। प्रत्येक [[ बहुफलकीय ग्राफ ]] में एक क्रिसमस कैक्टस सबग्राफ होता है जिसमें इसके सभी कोने शामिल होते हैं, एक ऐसा तथ्य जो एक सबूत में एक आवश्यक भूमिका निभाता है {{harvtxt|Leighton|Moitra|2010}} कि हर बहुफलकीय ग्राफ में [[यूक्लिडियन विमान]] में एक [[लालची एम्बेडिंग]] है, शीर्षों के लिए निर्देशांकों का एक असाइनमेंट जिसके लिए [[भौगोलिक रूटिंग]] शीर्षों के सभी जोड़े के बीच संदेशों को रूट करने में सफल होता है।<ref>{{citation
 | last1 = Leighton | first1 = Tom |author-link1= F. Thomson Leighton
 | last2 = Moitra | first2 = Ankur
 | issue = 3
 | journal = [[Discrete & Computational Geometry]]
 | pages = 686–705
 | title = Some Results on Greedy Embeddings in Metric Spaces
 | volume = 44
 | doi = 10.1007/s00454-009-9227-6
 | url = http://people.csail.mit.edu/moitra/docs/dcg-greedy.pdf
 | year = 2010| s2cid = 11186402 | doi-access = free
 }}.</ref>
[[टोपोलॉजिकल ग्राफ सिद्धांत]] में, ग्राफ़ जिनके [[ग्राफ एम्बेडिंग]] सभी प्लैनर ग्राफ़ हैं, वे कैक्टस ग्राफ़ के उपफ़ैमिली हैं, अतिरिक्त संपत्ति के साथ जो कि प्रत्येक वर्टेक्स अधिकतम एक चक्र से संबंधित है। इन ग्राफ़ में दो वर्जित अवयस्क, डायमंड ग्राफ़ और फाइव-वर्टेक्स फ्रेंडशिप ग्राफ़ हैं।<ref>{{citation
 | last1 = Nordhaus | first1 = E. A.
 | last2 = Ringeisen | first2 = R. D.
 | last3 = Stewart | first3 = B. M.
 | last4 = White | first4 = A. T.
 | doi = 10.1016/0095-8956(72)90040-8
 | journal = Journal of Combinatorial Theory
 | mr = 0299523
 | pages = 260–267
 | series = Series B
 | title = A Kuratowski-type theorem for the maximum genus of a graph
 | volume = 12
 | issue = 3
 | year = 1972| doi-access = free
 }}</ref>


== इतिहास ==

कोडी हुसिमी द्वारा इन रेखांकन पर पिछले काम के सम्मान में [[फ्रैंक हैरिस]] और [[जॉर्ज यूजीन उहलेनबेक]] द्वारा उन्हें दिए गए हुसिमी पेड़ों के नाम के तहत पहली बार कैक्टी का अध्ययन किया गया था।<ref>{{citation |last1=Harary |first1=Frank |last2=Uhlenbeck |author-link1 = Frank Harary |first2=George E. |author-link2=George Eugene Uhlenbeck |title=On the number of Husimi trees, I |journal=[[Proceedings of the National Academy of Sciences]] |volume=39 |year=1953 |pages=315–322 |mr=0053893 |doi=10.1073/pnas.39.4.315 |issue=4|pmid=16589268 |pmc=1063779|bibcode=1953PNAS...39..315H |doi-access=free }}</ref><ref>{{citation |last=Husimi |first=Kodi |title=Note on Mayers' theory of cluster integrals |journal=Journal of Chemical Physics |volume=18 |year=1950 |pages=682–684 |mr=0038903 |doi=10.1063/1.1747725 |issue=5|bibcode=1950JChPh..18..682H }}</ref> वही हरारी-उहलेनबेक पेपर इस प्रकार के ग्राफ़ के लिए कैक्टस नाम सुरक्षित रखता है जिसमें प्रत्येक चक्र एक त्रिभुज है, लेकिन अब सभी लंबाई के चक्रों को अनुमति देना मानक है।

इस बीच, हुसिमी पेड़ का नाम आमतौर पर ग्राफ़ को संदर्भित करने के लिए आया था जिसमें ग्राफ़ सिद्धांत का प्रत्येक शब्दकोष एक पूर्ण ग्राफ़ है (समतुल्य रूप से, किसी अन्य ग्राफ़ में ब्लॉक के प्रतिच्छेदन ग्राफ़)। इस प्रयोग का हुसिमी के काम से बहुत कम लेना-देना था, और अधिक प्रासंगिक शब्द ब्लॉक ग्राफ अब इस परिवार के लिए उपयोग किया जाता है; हालाँकि, इस अस्पष्टता के कारण यह वाक्यांश कैक्टस ग्राफ़ को संदर्भित करने के लिए कम बार उपयोग किया जाता है।<ref>See, e.g., {{MR|0659742}}, 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]].</ref>


==संदर्भ==
{{reflist|colwidth=30em}}


==बाहरी संबंध==
*[http://www.angelfire.com/electronic2/cas/ Application of Cactus Graphs in Analysis and Design of Electronic Circuits]
[[Category: ग्राफ परिवार]] [[Category: प्लानर रेखांकन]] [[Category: एकीकृत सर्किट]] 



[[Category: Machine Translated Page]]
[[Category:Created On 08/05/2023]]