सघन ग्राफ

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

सरल आरेख़ के आरेख़ घनत्व को अधिकतम संभव किनारों के संबंध में किनारों की संख्या |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, 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 शीर्षों वाले किसी भी समतलीय आरेख में अधिकतम 3n – 6 किनारे होते हैं, और समतलीय (3 से कम शीर्षों वाले आरेख़ को छोड़कर), आरेख़ का कोई भी उपआरेख़ समतलीय होता है, साथ में यह संकेत मिलता है कि समतलीय आरेख़ (3,6)-विरल हैं । यद्यपि, प्रत्येक (3,6)-विरल आरेख समतलीय नहीं है। इसी प्रकार, बाह्यतलीय आरेख (2,3)-विरल हैं और समतलीय द्विदलीय आरेख (2,4)-विरल हैं ।

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

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

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

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

सीमाबद्ध अध:पतन वाले और कहीं भी सघन आरेख़ वाले आरेख़ के वर्ग दोनों को बाइसिकल-मुक्त आरेख़, आरेख़ समूहों में शामिल किया गया है जो कुछ पूर्ण द्विदलीय आरेख़ को उपआरेख़ के रूप में बाहर करते हैं (Telle & Villanger 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।