मोंगे सरणी

कंप्यूटर विज्ञान पर लागू गणित में, मोंगे सरणी, या मोंगे आव्यूह, गणितीय वस्तुएं हैं जिनका नाम उनके खोजकर्ता, फ्रांसीसी गणितज्ञ गैसपार्ड मोंगे के नाम पर रखा गया है।

एक m-by-n आव्यूह (गणित) को मोंगे सरणी कहा जाता है, यदि सभी के लिए $\scriptstyle i,\,j,\,k,\,\ell$ इस प्रकार है कि

$1\leq i<k\leq m{\text{ and }}1\leq j<\ell \leq n$

एक को निम्न प्राप्त होता है

$A[i,j]+A[k,\ell ]\leq A[i,\ell ]+A[k,j].\,$

तो मोंगे सरणी (एक 2 × 2 उप-आव्यूह) की किन्हीं दो पंक्तियों और दो स्तंभों के लिए प्रतिच्छेदन बिंदुओं पर चार तत्वों में यह गुण होता है कि ऊपरी-बाएँ और निचले दाएँ तत्वों का योग (मुख्य विकर्ण के पार) निचले-बाएँ और ऊपरी-दाएँ तत्वों (प्रतिविकर्ण के पार) के योग से कम या उसके बराबर होता है ।

यह आव्यूह एक मोंगे सरणी है:

${\begin{bmatrix}10&17&13&28&23\\17&22&16&29&23\\24&28&22&34&24\\11&13&6&17&7\\45&44&32&37&23\\36&33&19&21&6\\75&66&51&53&34\end{bmatrix}}$

उदाहरण के लिए, पंक्ति 1 और 5 के साथ पंक्ति 2 और 4 का प्रतिच्छेदन लें।

चार तत्व निम्न हैं:

${\begin{bmatrix}17&23\\11&7\end{bmatrix}}$

17 + 7 = 24

23 + 11 = 34

ऊपरी-बाएँ और निचले दाएँ तत्वों का योग निचले-बाएँ और ऊपरी-दाएँ तत्वों के योग से कम या उसके बराबर है।

गुण

• उपरोक्त परिभाषा कथन के समतुल्य है

एक आव्यूह एक स्पंज सरणी है यदि और केवल यदि $A[i,j]+A[i+1,j+1]\leq A[i,j+1]+A[i+1,j]$ सभी के लिए $1\leq i<m$ और $1\leq j<n$ है।

• मूल मोंगे सरणी से कुछ पंक्तियों और स्तंभों का चयन करके निर्मित कोई भी उपसरणी स्वयं एक मोंगे सरणी होगी।
• मोंगे सरणियों के गैर-नकारात्मक गुणांक वाला कोई भी रैखिक संयोजन स्वयं एक मोंगे सरणी है।
• मोंगे सरणियों की एक रोचक विशेषता यह है कि यदि आप प्रत्येक पंक्ति के सबसे बाईं ओर एक वृत्त के साथ चिह्नित करते हैं, तो आप पाएंगे कि आपके वृत्त दाईं ओर नीचे की ओर बढ़ते हैं; कहने का तात्पर्य यह है कि यदि $f(x)=\arg \min _{i\in \{1,\ldots ,m\}}A[x,i]$, तब $f(j)\leq f(j+1)$ सभी के लिए $1\leq j<n$ है। सममित रूप से, यदि आप प्रत्येक पंक्ति के सबसे ऊपरी न्यूनतम को चिह्नित करते हैं, तो आपकी मंडलियां दाएं और नीचे की ओर प्रगति करेंगी। पंक्ति और स्तंभ मैक्सिमा विपरीत दिशा में चलते हैं: ऊपर से दाईं ओर और नीचे से बाईं ओर।
• शक्तिहीन मोंगे सरणियों की धारणा प्रस्तावित की गई है; एक शक्तिहीन मोंगे सरणी एक वर्ग n-by-n आव्यूह है जो सभी $1\leq i<r,s\leq n$ के लिए मोंगे विशेषता $A[i,i]+A[r,s]\leq A[i,s]+A[r,i]$ को संतुष्ट करती है।
• प्रत्येक मोंगे सरणी पूरी तरह से एकरस है, जिसका अर्थ है कि इसकी पंक्ति न्यूनतम स्तंभों के गैर-घटते अनुक्रम में होती है, और यह कि प्रत्येक उपसरणी के लिए समान गुण सत्य है। यह विशेषता स्मॉक कलन विधि का उपयोग करके पंक्ति मिनिमा को शीघ्रता से ढूंढने की अनुमति देती है।
• मोन्ज आव्यूह दो अलग-अलग चरों के उपप्रतिरूपक फलन का दूसरा नाम है। संक्षेप में, A एक मोंगे आव्यूह है यदि और केवल यदि A[i,j] चर i,j का एक उपप्रतिरूपक फलन है।

अनुप्रयोग

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

संदर्भ

• Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "ट्रैवलिंग सेल्समैन, डार्ट बोर्ड और यूरो-सिक्के से जुड़ी कुछ समस्याएं" (PDF). सैद्धांतिक कंप्यूटर विज्ञान के लिए यूरोपीय संघ का बुलेटिन. ईएटीसीएस. 90: 43–52. ISSN 0252-9742.