सघन ग्राफ

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

सरल ग्राफ़ के ग्राफ़ घनत्व को किनारों की संख्या के अनुपात के रूप में परिभाषित किया गया है |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 है (Coleman & Moré 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)।

विरल और तंग ग्राफ

Lee & Streinu (2008) और Streinu & Theran (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)-स्पार्स परिवार में बंधे हुए अध:पतन (ग्राफ सिद्धांत) या बंधे हुए आर्बोरिसिटी वाले ग्राफ़ के बराबर है। अधिक सटीक रूप से, यह एक परिणाम से आता है Nash-Williams (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.