कैक्टस ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
 
(14 intermediate revisions by 3 users not shown)
Line 3: Line 3:


== गुण ==
== गुण ==
कैक्टि [[आउटरप्लानर ग्राफ]] हैं। हर [[ seudoforest |स्यूडोफ़ॉरेस्ट]] एक कैक्टस है। एक गैर-तुच्छ ग्राफ एक कैक्टस है यदि और केवल यदि प्रत्येक ब्लॉक (यह ग्राफ थ्योरी की शब्दावली है।) या तो एक सरल चक्र (ग्राफ सिद्धांत) या एक किनारा है।
कैक्टि [[आउटरप्लानर ग्राफ]] हैं। हर [[ 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>
ग्राफ़ का परिवार जिसमें प्रत्येक घटक (ग्राफ़ सिद्धांत) एक कैक्टस होता है, ग्राफ़ लघु संचालन के तहत [[नीचे की ओर बंद]] होता है। इस ग्राफ़ परिवार को एक एकल फॉरबिडेन माइनर द्वारा चित्रित किया जा सकता है, पूर्ण ग्राफ़ ''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|मैत्री ग्राफ त्रिकोणीय कैक्टि हैं]]एक त्रिकोणीय कैक्टस एक विशेष प्रकार का कैक्टस ग्राफ है जैसे कि प्रत्येक चक्र की लंबाई तीन होती है और प्रत्येक किनारा एक चक्र से संबंधित होता है। उदाहरण के लिए, मित्रता रेखांकन, त्रिभुजों के संग्रह से बने रेखांकन एक ही साझा शीर्ष पर एक साथ जुड़ते हैं, त्रिकोणीय कैक्टि होते हैं। कैक्टस ग्राफ़ होने के साथ-साथ त्रिकोणीय कैक्टि [[ब्लॉक ग्राफ]]़ और स्थानीय रेखीय ग्राफ़ भी हैं।
[[File:Friendship graphs.svg|thumb|upright=1.6|मैत्री ग्राफ त्रिकोणीय कैक्टि हैं]]एक त्रिकोणीय कैक्टस एक विशेष प्रकार का कैक्टस ग्राफ है जैसे कि प्रत्येक चक्र की लंबाई तीन होती है और प्रत्येक किनारा एक चक्र से संबंधित होता है। उदाहरण के लिए, मित्रता रेखांकन, त्रिभुजों के संग्रह से बने रेखांकन एक ही साझा शीर्ष पर एक साथ जुड़ते हैं, त्रिकोणीय कैक्टि होते हैं। कैक्टस ग्राफ़ होने के साथ-साथ त्रिकोणीय कैक्टि [[ब्लॉक ग्राफ]] और स्थानीय रेखीय ग्राफ़ भी हैं।


त्रिकोणीय कैक्टस में यह गुण होता है कि यदि कोई [[मिलान (ग्राफ सिद्धांत)]] उनसे हटा दिया जाए तो वे जुड़े रहते हैं; दिए गए शीर्षों की संख्या के लिए, उनके पास इस गुण के साथ सबसे कम संभव किनारे होते हैं। विषम संख्या में कोने वाले प्रत्येक पेड़ को किनारों को जोड़कर त्रिकोणीय कैक्टस में बढ़ाया जा सकता है,
त्रिकोणीय कैक्टस में यह गुण होता है कि यदि कोई [[मिलान (ग्राफ सिद्धांत)]] हटा दिया जाता है तो भी वे जुड़े रहते हैं; दिए गए शीर्षों की संख्या के लिए, उनके पास इस गुण के साथ सबसे कम संभव किनारे होते हैं। कोने की एक विषम संख्या वाले प्रत्येक पेड़ को एक त्रिकोणीय कैक्टस में किनारों को जोड़कर बढ़ाया जा सकता है, जो एक मिलान को हटाने के पश्चात जुड़े रहने के गुण के साथ न्यूनतम वृद्धि प्रदान करता है।<ref>{{citation
एक मिलान को हटाने के बाद जुड़े रहने की संपत्ति के साथ न्यूनतम वृद्धि देना।<ref>{{citation
  | last1 = Farley | first1 = Arthur M.
  | last1 = Farley | first1 = Arthur M.
  | last2 = Proskurowski | first2 = Andrzej
  | last2 = Proskurowski | first2 = Andrzej
Line 21: Line 20:
  | volume = 12
  | volume = 12
  | year = 1982}}</ref>
  | year = 1982}}</ref>
किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ [[प्लेनर ग्राफ]]़ हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का [[सन्निकटन अनुपात]] 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।<ref>{{citation
 
किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ [[प्लेनर ग्राफ]] हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण (ग्राफ़ थ्योरी के गणितीय क्षेत्र ) में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का [[सन्निकटन अनुपात]] 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।<ref>{{citation
  | last1 = Călinescu | first1 = Gruia
  | last1 = Călinescu | first1 = Gruia
  | last2 = Fernandes | first2 = Cristina G
  | last2 = Fernandes | first2 = Cristina G
Line 36: Line 36:
  | s2cid = 8329680
  | s2cid = 8329680
  }}</ref>
  }}</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>
सबसे बड़े त्रिकोणीय कैक्टस को खोजने के लिए एल्गोरिदम लोवाज़ और प्लमर के प्रमेय से जुड़ा हुआ है जो इस सबसे बड़े कैक्टस में त्रिकोणों की संख्या को दर्शाता है।<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>\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>\sum_{i=1}^{m}\frac{(u_i - 1)}{2} + n - k,</math>,
कहाँ <math>n</math> दिए गए ग्राफ में शीर्षों की संख्या है और <math>u_i</math> एज क्लास द्वारा मिले वर्टेक्स क्लास की संख्या है <math>E_i</math>.
जहां <math>n</math> दिए गए ग्राफ में शीर्षों की संख्या है और <math>u_i</math> एज वर्गों द्वारा मिले शीर्ष वर्गों की संख्या है <math>E_i</math>.


हाल ही में, एक तंग चरम सीमा सिद्ध हुई थी<ref>{{citation
हाल ही में, एक तंग चरम सीमा सिद्ध हुई थी<ref>{{citation
Line 56: Line 59:
  | title = 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany
  | title = 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany
  | volume = 126
  | volume = 126
  | year = 2019}}</ref> जिसने दिखाया कि किसी भी [[समतल ग्राफ]] को दिया गया है <math>G</math>, हमेशा एक कैक्टस सबग्राफ मौजूद होता है <math>C \subseteq G</math> कम से कम युक्त <math>1/6</math> के त्रिकोणीय चेहरों का अंश <math>G</math>. यह परिणाम उपरोक्त न्यूनतम-अधिकतम सूत्र का उपयोग किए बिना अधिकतम प्लानर सबग्राफ समस्या के लिए 4/9 - सन्निकटन एल्गोरिथ्म का प्रत्यक्ष विश्लेषण दर्शाता है।
  | 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> ज्यादा ठीक
त्रिकोणीय कैक्टस से संबंधित एक महत्वपूर्ण अनुमान रोजा का अनुमान है, जिसका नाम अलेक्जेंडर रोजा के नाम पर रखा गया है, जो कहता है कि सभी त्रिकोणीय कैक्टि सुन्दर या लगभग सुन्दर हैं।<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 वाले ग्रेसफुल हैं।
टी ≡ 0, 1 मॉड 4 ब्लॉक वाले सभी त्रिकोणीय कैक्टि सुन्दर हैं, और टी ≡ 2, 3 मॉड 4 वाले सुन्दर हैं।


== एल्गोरिदम और अनुप्रयोग ==
== एल्गोरिदम और अनुप्रयोग ==
Line 73: Line 76:
विभिन्न जीनोम या जीनोम के कुछ हिस्सों के बीच संबंधों का प्रतिनिधित्व करने के उपायो के रूप में कैक्टि का उपयोग [[तुलनात्मक जीनोमिक्स]] में भी किया गया है।<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>
विभिन्न जीनोम या जीनोम के कुछ हिस्सों के बीच संबंधों का प्रतिनिधित्व करने के उपायो के रूप में कैक्टि का उपयोग [[तुलनात्मक जीनोमिक्स]] में भी किया गया है।<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|लीटन और|मोइत्रा|2010}} द्वारा एक प्रमाण में एक आवश्यक भूमिका निभाता है कि हर बहुफलकीय ग्राफ में [[यूक्लिडियन विमान]] में एक [[लालची एम्बेडिंग|भौगोलिक रूटिंग]] है, शीर्षों के लिए निर्देशांकों का एक कार्य जिसके लिए [[भौगोलिक रूटिंग]] शीर्षों के सभी युग्मों के बीच संदेशों को मार्ग करने में सफल होता है।<ref>{{citation
यदि एक कैक्टस जुड़ा हुआ है, और इसका प्रत्येक शीर्ष अधिकतम दो ब्लॉकों से संबंधित है, तो इसे क्रिसमस कैक्टस कहा जाता है। प्रत्येक [[ बहुफलकीय ग्राफ | बहुफलकीय ग्राफ]] में एक क्रिसमस कैक्टस सबग्राफ होता है जिसमें इसके सभी कोने सम्मलित होते हैं, एक ऐसा तथ्य जो {{harvtxt|लीटन और|मोइत्रा|2010}} द्वारा एक प्रमाण में एक आवश्यक भूमिका निभाता है कि हर बहुफलकीय ग्राफ में [[यूक्लिडियन विमान]] में एक [[लालची एम्बेडिंग|भौगोलिक रूटिंग]] है, शीर्षों के लिए निर्देशांकों का एक कार्य जिसके लिए [[भौगोलिक रूटिंग]] शीर्षों के सभी युग्मों के बीच संदेशों को मार्ग करने में सफल होता है।<ref>{{citation
  | last1 = Leighton | first1 = Tom |author-link1= F. Thomson Leighton
  | last1 = Leighton | first1 = Tom |author-link1= F. Thomson Leighton
  | last2 = Moitra | first2 = Ankur
  | last2 = Moitra | first2 = Ankur
Line 86: Line 89:
  }}.</ref>
  }}.</ref>


[[टोपोलॉजिकल ग्राफ सिद्धांत]] में, ग्राफ़ जिनके [[ग्राफ एम्बेडिंग]] सभी प्लैनर ग्राफ़ हैं, वे कैक्टस ग्राफ़ के उपफ़ैमिली हैं, अतिरिक्त संपत्ति के साथ जो कि प्रत्येक वर्टेक्स अधिकतम एक चक्र से संबंधित है। इन ग्राफ़ में दो वर्जित अवयस्क, डायमंड ग्राफ़ और फाइव-वर्टेक्स फ्रेंडशिप ग्राफ़ हैं।<ref>{{citation
[[टोपोलॉजिकल ग्राफ सिद्धांत]] में, वे ग्राफ़ जिनके [[ग्राफ एम्बेडिंग|सेलुलर एम्बेडिंग]] सभी प्लैनर ग्राफ़ हैं, कैक्टस ग्राफ़ के उपपरिवार हैं, अतिरिक्त गुणधर्म के साथ जो कि प्रत्येक शीर्ष अधिकतम एक चक्र से संबंधित है। इन ग्राफ़ में दो वर्जित अवयस्क, डायमंड ग्राफ़ और पांच शीर्ष फ्रेंडशिप ग्राफ़ हैं।<ref>{{citation
  | last1 = Nordhaus | first1 = E. A.
  | last1 = Nordhaus | first1 = E. A.
  | last2 = Ringeisen | first2 = R. D.
  | last2 = Ringeisen | first2 = R. D.
Line 106: Line 109:
कोडी हुसिमी द्वारा इन रेखांकन पर पिछले काम के सम्मान में [[फ्रैंक हैरिस]] और [[जॉर्ज यूजीन उहलेनबेक]] द्वारा उन्हें दिए गए हुसिमी पेड़ों के नाम के तहत पहली बार कैक्टी का अध्ययन किया गया था।<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>{{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>
इस बीच, हुसिमी पेड़ का नाम सामान्यतः उन ग्राफ़ों को संदर्भित करने के लिए आया था जिनमें प्रत्येक ब्लॉक (यह ग्राफ थ्योरी की शब्दावली) एक पूर्ण ग्राफ़ है (समतुल्य रूप से, किसी अन्य ग्राफ़ में ब्लॉक के प्रतिच्छेदन ग्राफ़)। इस प्रयोग का हुसिमी के काम से बहुत कम लेना-देना था, और अधिक प्रासंगिक शब्द ब्लॉक ग्राफ अब इस परिवार के लिए उपयोग किया जाता है; चूंकि, इस अस्पष्टता के कारण यह वाक्यांश कैक्टस ग्राफ़ को संदर्भित करने के लिए बहुत कम उपयोग किया जाता है।<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}}
{{reflist|colwidth=30em}}
Line 112: Line 115:
==बाहरी संबंध==
==बाहरी संबंध==
*[http://www.angelfire.com/electronic2/cas/ इलेक्ट्रॉनिक सर्किट के विश्लेषण और अभिकल्प में कैक्टस ग्राफ का अनुप्रयोग]
*[http://www.angelfire.com/electronic2/cas/ इलेक्ट्रॉनिक सर्किट के विश्लेषण और अभिकल्प में कैक्टस ग्राफ का अनुप्रयोग]
[[Category: ग्राफ परिवार]] [[Category: प्लानर रेखांकन]] [[Category: एकीकृत सर्किट]]


[[Category: Machine Translated Page]]
[[Category:Articles with Russian-language sources (ru)]]
[[Category:Created On 08/05/2023]]
[[Category:Created On 08/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:एकीकृत सर्किट]]
[[Category:ग्राफ परिवार]]
[[Category:प्लानर रेखांकन]]

Latest revision as of 16:29, 24 May 2023

कैक्टस ग्राफ

ग्राफ सिद्धांत में, एक कैक्टस (कभी-कभी कैक्टस ट्री कहा जाता है) एक जुड़ा हुआ ग्राफ होता है जिसमें किसी भी दो सरल चक्रों (ग्राफ सिद्धांत) में अधिकतम एक शीर्ष (ग्राफ सिद्धांत) सामान्य होता है। समतुल्य रूप से, यह एक जुड़ा हुआ ग्राफ है जिसमें प्रत्येक किनारा अधिक से अधिक एक साधारण चक्र से संबंधित होता है, या (असतहीय कैक्टस के लिए) जिसमें प्रत्येक ब्लॉक (कट-वर्टेक्स के बिना अधिकतम सबग्राफ) एक किनारा या एक चक्र होता है।

गुण

कैक्टि आउटरप्लानर ग्राफ हैं। हर स्यूडोफ़ॉरेस्ट एक कैक्टस है। एक असतहीय ग्राफ एक कैक्टस है यदि और केवल यदि प्रत्येक ब्लॉक (यह ग्राफ थ्योरी की शब्दावली है।) या तो एक सरल चक्र (ग्राफ सिद्धांत) या एक किनारा है।

ग्राफ़ का परिवार जिसमें प्रत्येक घटक (ग्राफ़ सिद्धांत) एक कैक्टस होता है, ग्राफ़ लघु संचालन के तहत नीचे की ओर बंद होता है। इस ग्राफ़ परिवार को एक एकल फॉरबिडेन माइनर द्वारा चित्रित किया जा सकता है, पूर्ण ग्राफ़ K4 से एक किनारे को हटाकर चार शीर्ष हीरा ग्राफ़ बनाया गया है।[1]

त्रिकोणीय कैक्टस

मैत्री ग्राफ त्रिकोणीय कैक्टि हैं

एक त्रिकोणीय कैक्टस एक विशेष प्रकार का कैक्टस ग्राफ है जैसे कि प्रत्येक चक्र की लंबाई तीन होती है और प्रत्येक किनारा एक चक्र से संबंधित होता है। उदाहरण के लिए, मित्रता रेखांकन, त्रिभुजों के संग्रह से बने रेखांकन एक ही साझा शीर्ष पर एक साथ जुड़ते हैं, त्रिकोणीय कैक्टि होते हैं। कैक्टस ग्राफ़ होने के साथ-साथ त्रिकोणीय कैक्टि ब्लॉक ग्राफ और स्थानीय रेखीय ग्राफ़ भी हैं।

त्रिकोणीय कैक्टस में यह गुण होता है कि यदि कोई मिलान (ग्राफ सिद्धांत) हटा दिया जाता है तो भी वे जुड़े रहते हैं; दिए गए शीर्षों की संख्या के लिए, उनके पास इस गुण के साथ सबसे कम संभव किनारे होते हैं। कोने की एक विषम संख्या वाले प्रत्येक पेड़ को एक त्रिकोणीय कैक्टस में किनारों को जोड़कर बढ़ाया जा सकता है, जो एक मिलान को हटाने के पश्चात जुड़े रहने के गुण के साथ न्यूनतम वृद्धि प्रदान करता है।[2]

किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ प्लेनर ग्राफ हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण (ग्राफ़ थ्योरी के गणितीय क्षेत्र ) में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का सन्निकटन अनुपात 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।[3]

सबसे बड़े त्रिकोणीय कैक्टस को खोजने के लिए एल्गोरिदम लोवाज़ और प्लमर के प्रमेय से जुड़ा हुआ है जो इस सबसे बड़े कैक्टस में त्रिकोणों की संख्या को दर्शाता है।[4]

लोवाज़ और प्लमर दिए गए ग्राफ़ के कोने और किनारों के विभाजन के जोड़े को उपसमुच्चय में मानते हैं, गुण के साथ ग्राफ के प्रत्येक त्रिकोण में शीर्ष विभाजन के एक वर्ग में दो कोने हैं या किनारे विभाजन के एक वर्ग में सभी तीन किनारे हैं; वे इस गुण के साथ विभाजन की एक जोड़ी को वैध कहते हैं।

फिर सबसे बड़े त्रिकोणीय कैक्टस में त्रिकोणों की संख्या अधिकतम, वैध विभाजनों के जोड़े के बराबर होती है और , का

,

जहां दिए गए ग्राफ में शीर्षों की संख्या है और एज वर्गों द्वारा मिले शीर्ष वर्गों की संख्या है .

हाल ही में, एक तंग चरम सीमा सिद्ध हुई थी[5] जिसने दिखाया कि किसी भी समतल ग्राफ को दिया गया , में हमेशा एक कैक्टस सबग्राफ उपस्थित होता है जिसमें कम से कम युक्त के त्रिकोणीय फलको का अंश है। यह परिणाम उपरोक्त न्यूनतम-अधिकतम सूत्र का उपयोग किए बिना अधिकतम प्लानर सबग्राफ समस्या के लिए 4/9 - सन्निकटन एल्गोरिथ्म का प्रत्यक्ष विश्लेषण दर्शाता है।

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

त्रिकोणीय कैक्टस से संबंधित एक महत्वपूर्ण अनुमान रोजा का अनुमान है, जिसका नाम अलेक्जेंडर रोजा के नाम पर रखा गया है, जो कहता है कि सभी त्रिकोणीय कैक्टि सुन्दर या लगभग सुन्दर हैं।[6] ज्यादा ठीक

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

एल्गोरिदम और अनुप्रयोग

कुछ सुविधा स्थान की समस्याएं (एफएलपी) जो सामान्य ग्राफ़ के लिए एनपी कठिन हैं, साथ ही कुछ अन्य ग्राफ़ समस्याएं कैक्टि के लिए बहुपद समय फलन (कंप्यूटर विज्ञान में, समय जटिलता) में हल की जा सकती हैं।[7][8]

चूंकि कैक्टि बाहरी प्लैनर ग्राफ के विशेष मामले हैं, बहुपद समय में ग्राफ पर कई संयोजी अनुकूलन समस्याओं को उनके लिए हल किया जा सकता है।[9]

कैक्टि विद्युत सर्किट का प्रतिनिधित्व करता है जिसमें उपयोगी गुण होते हैं। कैक्टि का एक प्रारंभिक अनुप्रयोग ऑप-एम्प्स के प्रतिनिधित्व से जुड़ा था।[10][11][12]

विभिन्न जीनोम या जीनोम के कुछ हिस्सों के बीच संबंधों का प्रतिनिधित्व करने के उपायो के रूप में कैक्टि का उपयोग तुलनात्मक जीनोमिक्स में भी किया गया है।[13]

यदि एक कैक्टस जुड़ा हुआ है, और इसका प्रत्येक शीर्ष अधिकतम दो ब्लॉकों से संबंधित है, तो इसे क्रिसमस क