सघन ग्राफ: Difference between revisions

Revision as of 20:57, 19 July 2023

गणित में, सघन आरेख़ एक ऐसा आरेख़ (असतत गणित) होता है जिसमें किनारों की संख्या किनारों की अधिकतम संख्या के निकट होती है (जहां शीर्ष (आरेख़ सिद्धांत) की प्रत्येक युग्म किनारे से संयोजित होती है)। इसके विपरीत, मात्र कुछ किनारों वाला आरेख विरल आरेख होता है। अतः सघन या विरल आरेख़ का निर्माण करने वाले का अंतर अपरिभाषित है, और इसे प्रायः 'लगभग बराबर' कथनों द्वारा दर्शाया जाता है। इसके कारण, घनत्व को परिभाषित करने की विधि प्रायः समस्या के संदर्भ पर निर्भर करता है।

इस प्रकार से सरल आरेख़ के आरेख़ घनत्व को अधिकतम संभव किनारों के संबंध में किनारों की संख्या $| E |$ के अनुपात के रूप में परिभाषित किया गया है।

अप्रत्यक्ष आरेख़ (असतत गणित) सरल आरेख़ के लिए, आरेख़ घनत्व है:

D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}

इस प्रकार से निर्देशित आरेख़, आरेख़ (असतत गणित) सरल आरेख़ के लिए, अधिकतम संभव किनारा अप्रत्यक्ष आरेख़ का दोगुना है (क्योंकि किनारे पर दो दिशाएँ होती हैं) इसलिए घनत्व है:

D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}

जहाँ $E$ किनारों की संख्या है और $V$ आरेख़ में शीर्षों की संख्या है। अप्रत्यक्ष आरेख़ के लिए किनारों की अधिकतम संख्या ${\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}$ है, इसलिए अधिकतम घनत्व 1 है (पूर्ण आरेख़ के लिए) और न्यूनतम घनत्व 0 है (कोलेमन & मोरे 1983)।

बढ़ते आकार के आरेख़ के समूहों के लिए, कोई प्रायः उन्हें विरल कहता है यदि $D\rightarrow 0$ को $|V|\rightarrow \infty$ के रूप में है। अतः कभी-कभी, कंप्यूटर विज्ञान में, विरल की अधिक प्रतिबंधात्मक परिभाषा का उपयोग किया जाता है जैसे $|E|=O(|V|\log |V|)$ या $|E|=O(|V|)$ ।

उध्र्व घनत्व

इस प्रकार से उध्र्व घनत्व परिमित आरेख़ से अनंत आरेख़ तक ऊपर परिभाषित आरेख़ घनत्व की अवधारणा का विस्तार है। सहज रूप से, अनंत आरेख़ में यादृच्छिक रूप से बड़े परिमित उपआरेख़ होते हैं जिनका घनत्व इसके उध्र्व घनत्व से कम होता है, और इसमें यादृच्छिक रूप से बड़े परिमित उपआरेख़ नहीं होते हैं जिनका घनत्व इसके उध्र्व घनत्व से अधिक होता है। औपचारिक रूप से, आरेख़ $G$ का उध्र्व घनत्व α मानों का न्यूनतम होता है, जैसे कि घनत्व α के साथ $G$ के परिमित उपसमूह में शीर्षों की एक सीमित संख्या होती है। अतः एर्डोस-स्टोन प्रमेय का उपयोग करके यह दिखाया जा सकता है कि उध्र्व घनत्व मात्र 1 या अतिविशिष्ट अनुपात $0, .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2, 2/3, 3/4, 4/5, … n/n + 1$ में से एक हो सकता है (देखें, उदाहरण के लिए, डायस्टेल, संस्करण 5, पृष्ठ 189)।

विरल और घन आरेख

इस प्रकार से ली & स्ट्रेइनु (2008) और स्ट्रेइनु & थेरान (2009) आरेख़ को $(k, l)$ विरल के रूप में परिभाषित करते हैं यदि $n$ शीर्षों वाले प्रत्येक गैर-रिक्त उपआरेख में अधिकतम $kn - l$ किनारे हैं, और $(k, l)$ -घऩ है यदि यह $(k, l)$ -विरल और इसमें निश्चित $kn - l$ किनारे हैं। अतः इस प्रकार ट्री (आरेख़ सिद्धांत) निश्चित $(1,1)$ -घन रेखांकन हैं, और निश्चित वैसे ही हैं $(1,1)$ -विरल आरेख़, और आर्बोरिसिटी $k$ वाले आरेख़ निश्चित $(k, k)$ -विरल आरेख़ हैं। छद्मवन वस्तुतः $(1,0)$ -विरल आरेख़ हैं, और कठोरता सिद्धांत (संरचनात्मक) में उत्पन्न होने वाले लमान आरेख वस्तुतः $(2,3)$ -घन रेखांकन हैं।

अतः अन्य आरेख समूहों को उनकी विरलता की विशेषता नहीं है, उन्हें भी इस प्रकार से वर्णित किया जा सकता है। इस प्रकार से उदाहरण के लिए, तथ्य यह है कि $n$ शीर्षों वाले किसी भी समतलीय आरेख में अधिकतम $3 n - 6$ किनारे होते हैं, और समतलीय (3 से कम शीर्षों वाले आरेख़ को छोड़कर), आरेख़ का कोई भी उपआरेख़ समतलीय होता है, साथ में यह संकेत मिलता है कि समतलीय आरेख़ $(3,6)$ -विरल हैं। यद्यपि, प्रत्येक $(3,6)$ -विरल आरेख समतलीय नहीं है। इसी प्रकार, बाह्यतलीय आरेख $(2,3)$ -विरल हैं और समतलीय द्विदलीय आरेख $(2,4)$ -विरल हैं।

इस प्रकार से स्ट्रेइनु और थेरान दिखाते हैं कि परीक्षण $(k, l)$ -विरलता बहुपद समय में किया जा सकता है जब $k$ और $l$ पूर्णांक होते हैं और $0 \leq l < 2 k$ होते हैं।

अतः एक आरेख़ समूह के लिए, $k$ और $l$ का अस्तित्व इस प्रकार है कि समूह में सभी आरेख $(k, l)$ -विरल हैं, जो समूह में सीमित अध:पतन (आरेख सिद्धांत) या सीमित आर्बोरिसिटी वाले आरेख़ के बराबर है। अधिक यथार्थ रूप से, यह नैश विलियम्स (1964) के परिणाम से ज्ञात होता है कि अधिकतम $a$ पर आर्बोरिसिटी के आरेख निश्चित $(a, a)$ -विरल आरेख़ हैं। इसी प्रकार अधिकतम $d$ पर अध:पतन के आरेख निश्चित $(d +1 / 2, 1)$ -विरल आरेख़ हैं।

आरेख़ के विरल और सघन वर्ग

अतः इस प्रकार से नेसेटेरिल & ओस्सोना डी मेंडेज़ (2010) ने माना कि विरलता/घनत्व द्विभाजन एकल आरेख उदाहरणों के अतिरिक्त अनंत आरेख वर्गों पर विचार करना आवश्यक बनाता है। उन्होंने कहीं सघन (आरेख़ सिद्धांत) आरेख़ वर्गों को आरेख़ के उन वर्गों के रूप में परिभाषित किया जिनके लिए देहली t- स्थित है जैसे कि प्रत्येक पूर्ण आरेख़ कक्षा में आरेख़ के उपआरेख़ में t-उपविभाजन के रूप में दिखाई देता है। इसके विपरीत, यदि ऐसी कोई सीमा स्थित नहीं है, तो वर्ग कहीं सघन है (आरेख़ सिद्धांत)। नेसेटेरिल & ओस्सोना डी मेंडेज़ (2012) में कहीं नहीं घने बनाम कहीं घने द्वंद्व के गुणों पर चर्चा की गई है।

इस प्रकार से सीमाबद्ध अध:पतन वाले और कहीं भी सघन आरेख़ वाले आरेख़ के वर्ग दोनों को द्विसमूह-मुक्त आरेख़, आरेख़ समूहों में सम्मिलित किया गया है जो कुछ पूर्ण द्विदलीय आरेख को उपआरेख़ के रूप में बाहर कर देते हैं (टेली & विलेंजर 2012)।

यह भी देखें

सीमाबद्ध विस्तार
सघन उपसमूह

संदर्भ

Paul E। Black, Sparse graph, from Dictionary of Algorithms and Data Structures, Paul E। Black (ed।), NIST। Retrieved on 29 September 2005।
Coleman, Thomas F.; Moré, Jorge J. (1983), "Estimation of sparse Jacobian matrices and graph coloring Problems", SIAM Journal on Numerical Analysis, 20 (1): 187–209, doi:10.1137/0720013।
Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575।
Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics, 308 (8): 1425–1437, arXiv:math/0702129, doi:10.1016/j.disc.2007.07.104, MR 2392060।
Nash-Williams, C. St. J. A. (1964), "Decomposition of finite graphs into forests", Journal of the London Mathematical Society, 39 (1): 12, doi:10.1112/jlms/s1-39.1.12, MR 0161333
Preiss, first (1998), Data Structures and Algorithms with Object-Oriented Design Patterns in C++, John Wiley & Sons, ISBN 0-471-24134-2।
Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2010), "From Sparse Graphs to Nowhere Dense Structures: Decompositions, Independence, Dualities and Limits", European Congress of Mathematics, European Mathematical Society, pp. 135–165
Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058।
Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics, 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018।
Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7501, Springer, pp. 802–812, doi:10.1007/978-3-642-33090-2_69।

@@ Line 1: / Line 1: @@
 {{short description|Graph with almost the max amount of edges}}
-गणित में, सघन आरेख़ एक ऐसा आरेख़ (असतत गणित) होता है जिसमें किनारों की संख्या किनारों की अधिकतम संख्या के निकट होती है (जहां [[वर्टेक्स (ग्राफ़ सिद्धांत)|शीर्ष (आरेख़ सिद्धांत)]] की प्रत्येक युग्म किनारे से संयोजित होती है)। इसके विपरीत, मात्र कुछ किनारों वाला आरेख विरल आरेख होता है। सघन या विरल आरेख़ का निर्माण करने वाले का अंतर अपरिभाषित है, और इसे प्रायः 'लगभग बराबर' कथनों द्वारा दर्शाया जाता है। इसके कारण, घनत्व को परिभाषित करने की विधि प्रायः समस्या के संदर्भ पर निर्भर करता है।
+गणित में, '''सघन आरेख़''' एक ऐसा '''आरेख़ (असतत गणित)''' होता है जिसमें किनारों की संख्या किनारों की अधिकतम संख्या के निकट होती है (जहां [[वर्टेक्स (ग्राफ़ सिद्धांत)|शीर्ष (आरेख़ सिद्धांत)]] की प्रत्येक युग्म किनारे से संयोजित होती है)। इसके विपरीत, मात्र कुछ किनारों वाला आरेख '''विरल आरेख''' होता है। अतः सघन या विरल आरेख़ का निर्माण करने वाले का अंतर अपरिभाषित है, और इसे प्रायः 'लगभग बराबर' कथनों द्वारा दर्शाया जाता है। इसके कारण, घनत्व को परिभाषित करने की विधि प्रायः समस्या के संदर्भ पर निर्भर करता है।
-सरल आरेख़ के आरेख़ घनत्व को अधिकतम संभव किनारों के संबंध में किनारों की संख्या {{math|{{abs|''E''}}}} के अनुपात के रूप में परिभाषित किया गया है।
+इस प्रकार से सरल आरेख़ के '''आरेख़ घनत्व''' को अधिकतम संभव किनारों के संबंध में किनारों की संख्या {{math|{{abs|''E''}}}} के अनुपात के रूप में परिभाषित किया गया है।
 अप्रत्यक्ष आरेख़ (असतत गणित) सरल आरेख़ के लिए, आरेख़ घनत्व है:
 :<math>D = \frac{|E|}{\binom {|V|}{2}} = \frac{2|E|}{|V|(|V|-1)}</math>
-[[निर्देशित ग्राफ|निर्देशित आरेख़]], आरेख़ (असतत गणित) सरल आरेख़ के लिए, अधिकतम संभव किनारा अप्रत्यक्ष आरेख़ का दोगुना है (क्योंकि किनारे पर दो दिशाएँ होती हैं) इसलिए घनत्व है:
+इस प्रकार से [[निर्देशित ग्राफ|निर्देशित आरेख़]], आरेख़ (असतत गणित) सरल आरेख़ के लिए, अधिकतम संभव किनारा अप्रत्यक्ष आरेख़ का दोगुना है (क्योंकि किनारे पर दो दिशाएँ होती हैं) इसलिए घनत्व है:
 :<math>D = \frac{|E|}{2{\binom {|V|}{2}}} = \frac{|E|}{|V|(|V|-1)}</math>
 जहाँ {{mvar|E}} किनारों की संख्या है और {{mvar|V}} आरेख़ में शीर्षों की संख्या है। अप्रत्यक्ष आरेख़ के लिए किनारों की अधिकतम संख्या <math>{\binom {|V|}{2}} = \frac{|V|(|V|-1)}2</math> है, इसलिए अधिकतम घनत्व 1 है (पूर्ण आरेख़ के लिए) और न्यूनतम घनत्व 0 है {{harv|कोलेमन|मोरे|1983}}।
-बढ़ते आकार के आरेख़ के समूहों के लिए, कोई प्रायः उन्हें विरल कहता है यदि <math>D \rightarrow 0</math> को <math>|V| \rightarrow \infty</math> के रूप में है। कभी-कभी, [[कंप्यूटर विज्ञान]] में, विरल की अधिक प्रतिबंधात्मक परिभाषा का उपयोग किया जाता है जैसे <math>|E| = O(|V| \log |V|)</math> या <math>|E| = O(|V|)</math>।
+बढ़ते आकार के आरेख़ के समूहों के लिए, कोई प्रायः उन्हें विरल कहता है यदि <math>D \rightarrow 0</math> को <math>|V| \rightarrow \infty</math> के रूप में है। अतः कभी-कभी, [[कंप्यूटर विज्ञान]] में, विरल की अधिक प्रतिबंधात्मक परिभाषा का उपयोग किया जाता है जैसे <math>|E| = O(|V| \log |V|)</math> या <math>|E| = O(|V|)</math>।
 ==उध्र्व घनत्व==
-उध्र्व घनत्व परिमित आरेख़ से अनंत आरेख़ तक ऊपर परिभाषित आरेख़ घनत्व की अवधारणा का विस्तार है। सहज रूप से, अनंत आरेख़ में यादृच्छिक रूप से बड़े परिमित उपआरेख़ होते हैं जिनका घनत्व इसके उध्र्व घनत्व से कम होता है, और इसमें यादृच्छिक रूप से बड़े परिमित उपआरेख़ नहीं होते हैं जिनका घनत्व इसके उध्र्व घनत्व से अधिक होता है। औपचारिक रूप से, आरेख़ {{mvar|G}} का उध्र्व घनत्व α मानों का न्यूनतम होता है, जैसे कि घनत्व α के साथ {{mvar|G}} के परिमित उपसमूह में शीर्षों की एक सीमित संख्या होती है। एर्डोस-स्टोन प्रमेय का उपयोग करके यह दिखाया जा सकता है कि उध्र्व घनत्व मात्र 1 या अतिविशिष्ट अनुपात {{math|0, {{sfrac|1|2}}, {{sfrac|2|3}}, {{sfrac|3|4}}, {{sfrac|4|5}}, … {{sfrac|''n''|''n'' + 1}}}} में से एक हो सकता है (देखें, उदाहरण के लिए, डायस्टेल, संस्करण 5, पृष्ठ 189)।
+इस प्रकार से उध्र्व घनत्व परिमित आरेख़ से अनंत आरेख़ तक ऊपर परिभाषित आरेख़ घनत्व की अवधारणा का विस्तार है। सहज रूप से, अनंत आरेख़ में यादृच्छिक रूप से बड़े परिमित उपआरेख़ होते हैं जिनका घनत्व इसके उध्र्व घनत्व से कम होता है, और इसमें यादृच्छिक रूप से बड़े परिमित उपआरेख़ नहीं होते हैं जिनका घनत्व इसके उध्र्व घनत्व से अधिक होता है। औपचारिक रूप से, आरेख़ {{mvar|G}} का उध्र्व घनत्व α मानों का न्यूनतम होता है, जैसे कि घनत्व α के साथ {{mvar|G}} के परिमित उपसमूह में शीर्षों की एक सीमित संख्या होती है। अतः एर्डोस-स्टोन प्रमेय का उपयोग करके यह दिखाया जा सकता है कि उध्र्व घनत्व मात्र 1 या अतिविशिष्ट अनुपात {{math|0, {{sfrac|1|2}}, {{sfrac|2|3}}, {{sfrac|3|4}}, {{sfrac|4|5}}, … {{sfrac|''n''|''n'' + 1}}}} में से एक हो सकता है (देखें, उदाहरण के लिए, डायस्टेल, संस्करण 5, पृष्ठ 189)।
 ==विरल और घन आरेख==
-{{harvtxt|ली|स्ट्रेइनु|2008}} और {{harvtxt|स्ट्रेइनु|थेरान|2009}} आरेख़ को {{math|(''k'', ''l'')}} विरल के रूप में परिभाषित करते हैं यदि {{mvar|n}} शीर्षों वाले प्रत्येक गैर-रिक्त उपआरेख में अधिकतम {{math|''kn'' − ''l''}} किनारे हैं, और {{math|(''k'', ''l'')}}-घऩ है यदि यह {{math|(''k'', ''l'')}}-विरल और इसमें निश्चित {{math|''kn'' − ''l''}} किनारे हैं। इस प्रकार [[वृक्ष (ग्राफ़ सिद्धांत)|ट्री (आरेख़ सिद्धांत)]] निश्चित {{math|(1,1)}}-घन रेखांकन हैं, और निश्चित वैसे ही हैं {{math|(1,1)}}-विरल आरेख़, और [[आर्बोरिसिटी]] {{mvar|k}} वाले आरेख़ निश्चित {{math|(''k'',''k'')}}-विरल आरेख़ हैं। [[छद्मवन]] वस्तुतः {{math|(1,0)}}-विरल आरेख़ हैं, और [[कठोरता सिद्धांत (संरचनात्मक)]] में उत्पन्न होने वाले [[लमान ग्राफ|लमान आरेख]] वस्तुतः {{math|(2,3)}}-घन रेखांकन हैं ।
+इस प्रकार से {{harvtxt|ली|स्ट्रेइनु|2008}} और {{harvtxt|स्ट्रेइनु|थेरान|2009}} आरेख़ को {{math|(''k'', ''l'')}} विरल के रूप में परिभाषित करते हैं यदि {{mvar|n}} शीर्षों वाले प्रत्येक गैर-रिक्त उपआरेख में अधिकतम {{math|''kn'' − ''l''}} किनारे हैं, और {{math|(''k'', ''l'')}}-घऩ है यदि यह {{math|(''k'', ''l'')}}-विरल और इसमें निश्चित {{math|''kn'' − ''l''}} किनारे हैं। अतः इस प्रकार [[वृक्ष (ग्राफ़ सिद्धांत)|ट्री (आरेख़ सिद्धांत)]] निश्चित {{math|(1,1)}}-घन रेखांकन हैं, और निश्चित वैसे ही हैं {{math|(1,1)}}-विरल आरेख़, और [[आर्बोरिसिटी]] {{mvar|k}} वाले आरेख़ निश्चित {{math|(''k'',''k'')}}-विरल आरेख़ हैं। [[छद्मवन]] वस्तुतः {{math|(1,0)}}-विरल आरेख़ हैं, और [[कठोरता सिद्धांत (संरचनात्मक)]] में उत्पन्न होने वाले [[लमान ग्राफ|लमान आरेख]] वस्तुतः {{math|(2,3)}}-घन रेखांकन हैं।
-अन्य आरेख समूहों को उनकी विरलता की विशेषता नहीं है, उन्हें भी इस प्रकार से वर्णित किया जा सकता है। उदाहरण के लिए, तथ्य यह है कि {{mvar|n}} शीर्षों वाले किसी भी [[समतलीय ग्राफ|समतलीय आरेख]] में अधिकतम {{math|3''n'' – 6}} किनारे होते हैं, और समतलीय (3 से कम शीर्षों वाले आरेख़ को छोड़कर), आरेख़ का कोई भी उपआरेख़ समतलीय होता है, साथ में यह संकेत मिलता है कि समतलीय आरेख़ {{math|(3,6)}}-विरल हैं । यद्यपि, प्रत्येक {{math|(3,6)}}-विरल आरेख समतलीय नहीं है। इसी प्रकार, [[बाह्यतलीय ग्राफ|बाह्यतलीय आरेख]] {{math|(2,3)}}-विरल हैं और समतलीय [[द्विदलीय ग्राफ|द्विदलीय आरेख]] {{math|(2,4)}}-विरल हैं ।
+अतः अन्य आरेख समूहों को उनकी विरलता की विशेषता नहीं है, उन्हें भी इस प्रकार से वर्णित किया जा सकता है। इस प्रकार से उदाहरण के लिए, तथ्य यह है कि {{mvar|n}} शीर्षों वाले किसी भी [[समतलीय ग्राफ|समतलीय आरेख]] में अधिकतम {{math|3''n'' – 6}} किनारे होते हैं, और समतलीय (3 से कम शीर्षों वाले आरेख़ को छोड़कर), आरेख़ का कोई भी उपआरेख़ समतलीय होता है, साथ में यह संकेत मिलता है कि समतलीय आरेख़ {{math|(3,6)}}-विरल हैं। यद्यपि, प्रत्येक {{math|(3,6)}}-विरल आरेख समतलीय नहीं है। इसी प्रकार, [[बाह्यतलीय ग्राफ|बाह्यतलीय आरेख]] {{math|(2,3)}}-विरल हैं और समतलीय [[द्विदलीय ग्राफ|द्विदलीय आरेख]] {{math|(2,4)}}-विरल हैं।
-स्ट्रेइनु और थेरान दिखाते हैं कि परीक्षण {{math|(''k'',''l'')}}-विरलता बहुपद समय में किया जा सकता है जब {{mvar|k}} और {{mvar|l}} पूर्णांक होते हैं और {{math|0 ≤ ''l'' < 2''k''}} होते हैं।
+इस प्रकार से स्ट्रेइनु और थेरान दिखाते हैं कि परीक्षण {{math|(''k'',''l'')}}-विरलता बहुपद समय में किया जा सकता है जब {{mvar|k}} और {{mvar|l}} पूर्णांक होते हैं और {{math|0 ≤ ''l'' < 2''k''}} होते हैं।
-एक आरेख़ समूह के लिए, {{mvar|k}} और {{mvar|l}} का अस्तित्व इस प्रकार है कि समूह में सभी आरेख {{math|(''k'',''l'')}}-विरल हैं, जो समूह में सीमित अध:पतन (आरेख सिद्धांत) या सीमित आर्बोरिसिटी वाले आरेख़ के बराबर है। अधिक यथार्थ रूप से, यह {{harvtxt|नैश विलियम्स|1964}} के परिणाम से ज्ञात होता है कि अधिकतम {{mvar|a}} पर आर्बोरिसिटी के आरेख निश्चित {{math|(''a'',''a'')}}-विरल आरेख़ हैं। इसी प्रकार अधोगति के आरेख भी अधिक से अधिक हैं {{mvar|d}} निश्चित हैं {{math|( {{sfrac|''d''+1|2}}, 1)}}-विरल आरेख़।
+अतः एक आरेख़ समूह के लिए, {{mvar|k}} और {{mvar|l}} का अस्तित्व इस प्रकार है कि समूह में सभी आरेख {{math|(''k'',''l'')}}-विरल हैं, जो समूह में सीमित अध:पतन (आरेख सिद्धांत) या सीमित आर्बोरिसिटी वाले आरेख़ के बराबर है। अधिक यथार्थ रूप से, यह {{harvtxt|नैश विलियम्स|1964}} के परिणाम से ज्ञात होता है कि अधिकतम {{mvar|a}} पर आर्बोरिसिटी के आरेख निश्चित {{math|(''a'',''a'')}}-विरल आरेख़ हैं। इसी प्रकार अधिकतम {{mvar|d}} पर अध:पतन के आरेख निश्चित {{math|( {{sfrac|''d''+1|2}}, 1)}}-विरल आरेख़ हैं।
 ==आरेख़ के विरल और सघन वर्ग==
-{{harvtxt|Nešetřil|Ossona de Mendez|2010}} माना जाता है कि विरलता/घनत्व द्विभाजन एकल आरेख़ उदाहरणों के बजाय अनंत आरेख़ वर्गों पर विचार करना आवश्यक बनाता है। उन्होंने कहीं सघन (आरेख़ थ्योरी) आरेख़ वर्गों को आरेख़ के उन वर्गों के रूप में परिभाषित किया जिनके लिए थ्रेसहोल्ड टी मौजूद है जैसे कि प्रत्येक पूर्ण आरेख़ कक्षा में आरेख़ के उपआरेख़ में टी-उपविभाजन के रूप में दिखाई देता है। इसके विपरीत, यदि ऐसी कोई सीमा मौजूद नहीं है, तो वर्ग कहीं सघन है (आरेख़ सिद्धांत)। कहीं सघन बनाम कहीं सघन द्वंद्व के गुणों पर चर्चा की गई है {{harvtxt|Nešetřil|Ossona de Mendez|2012}}।
+अतः इस प्रकार से {{harvtxt|नेसेटेरिल|ओस्सोना डी मेंडेज़|2010}} ने माना कि विरलता/घनत्व द्विभाजन एकल आरेख उदाहरणों के अतिरिक्त अनंत आरेख वर्गों पर विचार करना आवश्यक बनाता है। उन्होंने कहीं सघन (आरेख़ सिद्धांत) आरेख़ वर्गों को आरेख़ के उन वर्गों के रूप में परिभाषित किया जिनके लिए देहली t- स्थित है जैसे कि प्रत्येक पूर्ण आरेख़ कक्षा में आरेख़ के उपआरेख़ में t-उपविभाजन के रूप में दिखाई देता है। इसके विपरीत, यदि ऐसी कोई सीमा स्थित नहीं है, तो वर्ग कहीं सघन है (आरेख़ सिद्धांत)। {{harvtxt|नेसेटेरिल|ओस्सोना डी मेंडेज़|2012}} में कहीं नहीं घने बनाम कहीं घने द्वंद्व के गुणों पर चर्चा की गई है।
-सीमाबद्ध अध:पतन वाले और कहीं भी सघन आरेख़ वाले आरेख़ के वर्ग दोनों को [[बाइसिकल-मुक्त ग्राफ़|बाइसिकल-मुक्त आरेख़]], आरेख़ समूहों में शामिल किया गया है जो कुछ [[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विदलीय आरेख]]़ को उपआरेख़ के रूप में बाहर करते हैं {{harv|Telle|Villanger|2012}}।
+इस प्रकार से सीमाबद्ध अध:पतन वाले और कहीं भी सघन आरेख़ वाले आरेख़ के वर्ग दोनों को [[बाइसिकल-मुक्त ग्राफ़|द्विसमूह-मुक्त आरेख़]], आरेख़ समूहों में सम्मिलित किया गया है जो कुछ [[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विदलीय आरेख]] को उपआरेख़ के रूप में बाहर कर देते हैं {{harv|टेली|विलेंजर|2012}}।
 ==यह भी देखें==

Anonymous

Search

सघन ग्राफ: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:57, 19 July 2023

Contents

उध्र्व घनत्व

विरल और घन आरेख

आरेख़ के विरल और सघन वर्ग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सघन ग्राफ: Difference between revisions

Revision as of 20:57, 19 July 2023

उध्र्व घनत्व

विरल और घन आरेख

आरेख़ के विरल और सघन वर्ग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Hidden categories