यूनिट डिस्क ग्राफ

यूनिट वृत का संग्रह और संबंधित यूनिट डिस्क ग्राफ।

ज्यामितीय ग्राफ सिद्धांत में, यूनिट डिस्क ग्राफ यूक्लिडियन विमान में यूनिट डिस्क के एक परिवार का प्रतिच्छेदन ग्राफ है। यह परिवार में प्रत्येक डिस्क के लिए एक शीर्ष के साथ एक ग्राफ है और दो कोने के बीच एक किनारे के साथ जब भी संबंधित कोने एक दूसरे की एक इकाई दूरी के अन्दर होते हैं।

वे सामान्यतः एक प्वासों बिंदु प्रक्रिया से बनते हैं, जिससे उन्हें एक यादृच्छिक संरचना का एक सरल उदाहरण बना दिया जाता है।

परिभाषाएँ

यूनिट डिस्क ग्राफ़ की कई संभावित परिभाषाएँ एक दूसरे के बराबर होती हैं, जो स्केल फ़ैक्टर के विकल्प तक होती हैं:

• यूनिट डिस्क ग्राफ, यूक्लिडियन विमान में बिंदुओं के संग्रह से बना ग्राफ है, जिसमें प्रत्येक बिंदु के लिए एक शीर्ष और प्रत्येक जोड़ी बिंदुओं को जोड़ने वाला किनारा होता है, जिनकी दूरी एक निश्चित सीमा से नीचे होती है।
• यूनिट डिस्क ग्राफ़ समान-त्रिज्या वाले वृत्तों या समान-त्रिज्या वाले डिस्क के प्रतिच्छेदन ग्राफ़ हैं। इन ग्राफ़ों में प्रत्येक वृत्त या डिस्क के लिए एक शीर्ष होता है, और एक वृत्त या डिस्क के प्रत्येक युग्म को जोड़ने वाला किनारा होता है जिसमें एक गैर-खाली प्रतिच्छेदन होता है।
• जब भी एक वृत्त में दूसरे वृत्त का केंद्र होता है, तो दो वृत्तों को एक किनारे से जोड़कर, समान-त्रिज्या वाले वृत्तों के संग्रह से अलग विधि से यूनिट डिस्क ग्राफ़ बनाए जा सकते हैं।

गुण

यूनिट डिस्क ग्राफ़ का प्रत्येक प्रेरित सबग्राफ भी एक यूनिट डिस्क ग्राफ़ है। एक ग्राफ़ का एक उदाहरण जो एक यूनिट डिस्क ग्राफ़ नहीं है वह स्टार $K_{1,6}$ (ग्राफ़ सिद्धांत) है जिसमें एक केंद्रीय नोड छह पत्तियों से जुड़ा है: यदि छह इकाई डिस्क में से प्रत्येक एक सामान्य इकाई डिस्क को छूता है, तो छह डिस्क में से दो को एक दूसरे को छूना चाहिए। इसलिए, यूनिट डिस्क ग्राफ़ में एक प्रेरित $K_{1,6}$ सबग्राफ नहीं हो सकता है। असीम रूप से कई अन्य वर्जित प्रेरित सबग्राफ ज्ञात हैं।

$n$ लेबल वाले शीर्षों पर यूनिट डिस्क ग्राफ़ की संख्या $n^{2n}$के घातीय कारक के अन्दर है। इस तीव्र वृद्धि का अर्थ है कि यूनिट डिस्क ग्राफ़ में बाउंडेड ट्विन-चौड़ाई नहीं है।

अनुप्रयोग

के काम से शुरुआत की Huson & Sen (1995), मोबाइल तदर्थ नेटवर्क की टोपोलॉजी को मॉडल करने के लिए कंप्यूटर विज्ञान में यूनिट डिस्क ग्राफ़ का उपयोग किया गया है। इस एप्लिकेशन में, बेस स्टेशन के बिना सीधे वायरलेस कनेक्शन के माध्यम से नोड्स जुड़े हुए हैं। यह माना जाता है कि सभी नोड सजातीय हैं और सर्वदिशात्मक एंटेना से सुसज्जित हैं। नोड स्थानों को यूक्लिडियन बिंदुओं के रूप में प्रतिरूपित किया जाता है, और वह क्षेत्र जिसके अन्दर एक नोड से दूसरे नोड द्वारा एक संकेत प्राप्त किया जा सकता है, एक चक्र के रूप में प्रतिरूपित किया जाता है। यदि सभी नोड्स में समान शक्ति के ट्रांसमीटर हैं, तो ये वृत्त समान हैं। बेतरतीब ढंग से उत्पन्न डिस्क केंद्रों के साथ यूनिट डिस्क ग्राफ़ के रूप में गठित रैंडम ज्यामितीय ग्राफ़ का उपयोग परकोलेशन_थ्योरी और विभिन्न अन्य घटनाओं के मॉडल के रूप में भी किया गया है।

कम्प्यूटेशनल जटिलता

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

यह निर्धारित करने के लिए एनपी कठिन (अधिक विशेष रूप से, वास्तविक के अस्तित्व संबंधी सिद्धांत के लिए पूर्ण) है कि ज्यामिति के बिना दिए गए ग्राफ को यूनिट डिस्क ग्राफ के रूप में प्रदर्शित किया जा सकता है या नहीं। इसके अतिरिक्त, यह है provably इकाई डिस्क ग्राफ़ प्रतिनिधित्व के स्पष्ट निर्देशांक को आउटपुट करने के लिए बहुपद समय में असंभव: ऐसे यूनिट डिस्क ग्राफ़ मौजूद हैं जिन्हें ऐसे किसी भी प्रतिनिधित्व में सटीक रूप से कई बिट्स की आवश्यकता होती है। हालाँकि, कई महत्वपूर्ण और कठिन ग्राफ़ ऑप्टिमाइज़ेशन समस्याएँ जैसे कि अधिकतम स्वतंत्र सेट, ग्राफ रंग और न्यूनतम हावी सेट, इन ग्राफ़ों की ज्यामितीय संरचना का उपयोग करके कुशलतापूर्वक सन्निकटन एल्गोरिथम हो सकते हैं, और एक डिस्क प्रतिनिधित्व दिए जाने पर, बहुपद समय में इन ग्राफ़ों के लिए अधिकतम क्लिक समस्या को ठीक से हल किया जा सकता है। यहां तक ​​​​कि अगर एक डिस्क प्रतिनिधित्व ज्ञात नहीं है, और एक अमूर्त ग्राफ इनपुट के रूप में दिया गया है, तो बहुपद समय में यह संभव है कि या तो अधिकतम क्लिक या एक प्रमाण तैयार किया जाए कि ग्राफ एक इकाई डिस्क ग्राफ नहीं है, और 3-एक लालची रंग एल्गोरिथ्म का उपयोग करके इष्टतम रंग का अनुमान लगाना।

यह भी देखें

• बैरियर लचीलापन, यूनिट डिस्क ग्राफ़ में चक्र तोड़ने की एल्गोरिथम समस्या

उदासीनता का ग्राफ, यूनिट डिस्क ग्राफ का एक आयामी एनालॉग

• पेनी ग्राफ, यूनिट डिस्क ग्राफ जिसके लिए डिस्क स्पर्शरेखा हो सकती है लेकिन ओवरलैप नहीं (संपर्क ग्राफ)
• सिक्का ग्राफ, संपर्क ग्राफ (जरूरी नहीं कि इकाई-आकार) डिस्क
• विटोरिस-रिप्स कॉम्प्लेक्स, यूनिट डिस्क ग्राफ का एक सामान्यीकरण जो एक मीट्रिक स्पेस में यूनिट दूरी से उच्च-क्रम टोपोलॉजिकल रिक्त स्थान बनाता है
• यूनिट दूरी ग्राफ , एक ग्राफ जो उन बिंदुओं को जोड़कर बनता है जो किसी दिए गए थ्रेसहोल्ड पर (यहाँ के रूप में) के बजाय बिल्कुल एक दूरी पर हैं

संदर्भ

• Atminas, Aistis; Zamaraev, Viktor (2018), "On forbidden induced subgraphs for unit disk graphs", Discrete & Computational Geometry, 60 (1): 57–97, arXiv:1602.08148, doi:10.1007/s00454-018-9968-1, MR 3807349, S2CID 254025741
• Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters, 6 (6): 209–212, doi:10.1016/0020-0190(77)90070-9, MR 0489084{{citation}}: CS1 maint: multiple names: authors list (link).
• Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: small classes", Combinatorial Theory, 2 (2): P10:1–P10:42, arXiv:2006.09877, doi:10.5070/C62257876, MR 4449818
• Breu, Heinz; Kirkpatrick, David G. (1998), "Unit disk graph recognition is NP-hard", Computational Geometry: Theory and Applications, 9 (1–2): 3–24, doi:10.1016/s0925-7721(97)00014-x.
• Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O.
• Dall, Jesper; Christensen, Michael (2002), "Random geometric graphs", Physical Review E, 66 (1): 016121, arXiv:cond-mat/0203026, Bibcode:2002PhRvE..66a6121D, doi:10.1103/PhysRevE.66.016121, S2CID 15193516.
• Dębski, Michał; Junosza-Szaniawski, Konstanty; Śleszyńska-Nowak, Małgorzata (2020), "Strong chromatic index of $K_{1,t}$-free graphs", Discrete Applied Mathematics, 284: 53–60, doi:10.1016/j.dam.2020.03.024, MR 4115456, S2CID 216369782
• Gräf, A.; Stumpf, M.; Weißenfels, G. (1998), "On coloring unit disk graphs", Algorithmica, 20 (3): 277–293, doi:10.1007/PL00009196, MR 1489033, S2CID 36161020.
• Huson, Mark L.; Sen, Arunabha (1995), "Broadcast scheduling algorithms for radio networks", Military Communications Conference, IEEE MILCOM '95, vol. 2, pp. 647–651, doi:10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7, S2CID 62039740.
• Kang, Ross J.; Müller, Tobias (2011), "Sphere and dot product representations of graphs", Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SoCG'11), June 13–15, 2011, Paris, France, pp. 308–314.
• Marathe, Madhav V.; Breu, Heinz; Hunt, III, Harry B.; Ravi, S. S.; Rosenkrantz, Daniel J. (1994), Geometry based heuristics for unit disk graphs, arXiv:math.CO/9409226, Bibcode:1994math......9226M.
• Matsui, Tomomi (2000), Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs, Lecture Notes in Computer Science, vol. 1763, pp. 194–200, doi:10.1007/978-3-540-46515-7_16, ISBN 978-3-540-67181-7.
• McDiarmid, Colin; Mueller, Tobias (2013), "Integer realizations of disk and segment graphs", Journal of Combinatorial Theory, Series B, 103 (1): 114–143, arXiv:1111.2931, Bibcode:2011arXiv1111.2931M, doi:10.1016/j.jctb.2012.09.004
• McDiarmid, Colin; Müller, Tobias (2014), "The number of disk graphs", European Journal of Combinatorics, 35: 413–431, doi:10.1016/j.ejc.2013.06.037, MR 3090514
• Raghavan, Vijay; Spinrad, Jeremy (2003), "Robust algorithms for restricted domains", Journal of Algorithms, 48 (1): 160–172, doi:10.1016/S0196-6774(03)00048-8, MR 2006100, S2CID 16327087.