सघन ग्राफ

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

इस प्रकार से सरल आरेख़ के आरेख़ घनत्व को अधिकतम संभव किनारों के संबंध में किनारों की संख्या |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)-विरल आरेख़ हैं।

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

अतः इस प्रकार से नेसेटेरिल & ओस्सोना डी मेंडेज़ (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।