मोंगे सरणी

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

एक 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 उप-मैट्रिक्स) की किन्हीं दो पंक्तियों और दो स्तंभों के लिए प्रतिच्छेदन बिंदुओं पर चार तत्वों में यह गुण होता है कि ऊपरी-बाएँ और निचले दाएँ तत्वों का योग (मुख्य विकर्ण के पार) होता है निचले-बाएँ और ऊपरी-दाएँ तत्वों (प्रतिविकर्ण के पार) के योग से कम या उसके बराबर।

यह मैट्रिक्स एक Monge सरणी है:

${\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$.

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

अनुप्रयोग

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

संदर्भ

• Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "Some problems around travelling salesmen, dart boards, and euro-coins" (PDF). Bulletin of the European Association for Theoretical Computer Science. EATCS. 90: 43–52. ISSN 0252-9742.