दूरी मैट्रिक्स

गणित, कंप्यूटर विज्ञान और विशेष रूप से ग्राफ सिद्धांत में, एक दूरी मैट्रिक्स एक वर्ग मैट्रिक्स (द्वि-आयामी सरणी) है जिसमें एक सेट के तत्वों के बीच, जोड़ीदार दूरी ली जाती है। शामिल अनुप्रयोग के आधार पर, इस मैट्रिक्स को परिभाषित करने के लिए उपयोग की जाने वाली दूरी एक मीट्रिक (गणित) हो भी सकती है और नहीं भी। अगर वहाँ Nतत्व, इस मैट्रिक्स का आकार होगा N×N. ग्राफ़-सैद्धांतिक अनुप्रयोगों में तत्वों को अक्सर बिंदु, नोड या शीर्ष के रूप में संदर्भित किया जाता है।

गैर-मीट्रिक दूरी मैट्रिक्स

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

उपरोक्त का बीजगणितीय सूत्रीकरण न्यूनतम-प्लस बीजगणित का उपयोग करके प्राप्त किया जा सकता है। इस प्रणाली में मैट्रिक्स गुणन को इस प्रकार परिभाषित किया गया है: दो दिए गए हैं n × n मैट्रिक्स A = (a_ij) और B = (b_ij), उनका दूरी उत्पाद C = (c_ij) = A ⭑ B को एक के रूप में परिभाषित किया गया है n × n मैट्रिक्स ऐसा कि

$c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}.$

ध्यान दें कि ऑफ-विकर्ण तत्व जो सीधे जुड़े नहीं हैं, उन्हें सही ढंग से काम करने के लिए न्यूनतम-प्लस संचालन के लिए अनंत या उपयुक्त बड़े मूल्य पर सेट करने की आवश्यकता होगी। इन स्थानों में शून्य को गलत तरीके से एक किनारे के रूप में समझा जाएगा जिसमें कोई दूरी, लागत आदि नहीं होगी।

अगर W एक n × n मैट्रिक्स जिसमें एक ग्राफ़ (अलग गणित) का किनारा भार होता है W^k (इस दूरी उत्पाद का उपयोग करके) अधिकतम लंबाई के पथों का उपयोग करके शीर्षों के बीच की दूरी देता है kकिनारे, और Wⁿ ग्राफ़ का दूरी मैट्रिक्स है।

एक मनमाना ग्राफ G पर n शीर्षों को भारित पूर्ण ग्राफ के रूप में प्रतिरूपित किया जा सकता है n पूर्ण ग्राफ़ के प्रत्येक किनारे पर एक का भार निर्दिष्ट करके शीर्ष, जो कि एक किनारे से मेल खाता है G और अन्य सभी किनारों पर शून्य। W इस संपूर्ण ग्राफ़ के लिए आसन्नता मैट्रिक्स है G. की दूरी मैट्रिक्स G से गणना की जा सकती है W जैसा कि ऊपर बताया गया है, तथापि, Wⁿ सामान्य मैट्रिक्स गुणन द्वारा गणना केवल लंबाई के किन्हीं दो शीर्षों के बीच पथों की संख्या को सटीक रूप से एन्कोड करती है n.