मोंगे सरणी: Difference between revisions

From Vigyanwiki
(Created page with "{{refimprove|date=September 2012}} कंप्यूटर विज्ञान पर लागू गणित में, मोंगे ऐरे, या मों...")
 
(text)
Line 1: Line 1:
{{refimprove|date=September 2012}}
{{refimprove|date=September 2012}}
[[कंप्यूटर विज्ञान]] पर लागू गणित में, मोंगे ऐरे, या मोंगे मैट्रिसेस, गणितीय वस्तुएं हैं जिनका नाम उनके खोजकर्ता, फ्रांसीसी गणितज्ञ [[गैसपार्ड मोंगे]] के नाम पर रखा गया है।
[[कंप्यूटर विज्ञान]] पर लागू गणित में, '''मोंगे सरणी''', या मोंगे आव्यूह, गणितीय वस्तुएं हैं जिनका नाम उनके खोजकर्ता, फ्रांसीसी गणितज्ञ [[गैसपार्ड मोंगे]] के नाम पर रखा गया है।


एक ''m''-by-''n'' [[मैट्रिक्स (गणित)]] को ''मोंज ऐरे'' कहा जाता है, यदि सभी के लिए <math>\scriptstyle i,\, j,\, k,\, \ell</math> ऐसा है कि
एक ''m''-by-''n'' [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] को मोंगे सरणी कहा जाता है, यदि सभी के लिए <math>\scriptstyle i,\, j,\, k,\, \ell</math> इस प्रकार है कि


:<math>1\le i < k\le m\text{ and }1\le j < \ell\le n</math>
:<math>1\le i < k\le m\text{ and }1\le j < \ell\le n</math>
एक प्राप्त होता है<ref>{{cite journal
एक को निम्न प्राप्त होता है <ref>{{cite journal
| journal= Discrete Applied Mathematics
| journal= Discrete Applied Mathematics
| first1 = Rainer E. | last1 = Burkard
| first1 = Rainer E. | last1 = Burkard
Line 19: Line 19:
| doi-access = free}}</ref>
| doi-access = free}}</ref>
:<math>A[i,j] + A[k,\ell] \le A[i,\ell] + A[k,j].\,</math>
:<math>A[i,j] + A[k,\ell] \le A[i,\ell] + A[k,j].\,</math>
तो मोंज सरणी (एक 2 × 2 उप-मैट्रिक्स) की किन्हीं दो पंक्तियों और दो स्तंभों के लिए प्रतिच्छेदन बिंदुओं पर चार तत्वों में यह गुण होता है कि ऊपरी-बाएँ और निचले दाएँ तत्वों का योग ([[मुख्य विकर्ण]] के पार) होता है निचले-बाएँ और ऊपरी-दाएँ तत्वों ([[ प्रतिविकर्ण ]] के पार) के योग से कम या उसके बराबर।
तो मोंगे सरणी (एक 2 × 2 उप-आव्यूह) की किन्हीं दो पंक्तियों और दो स्तंभों के लिए प्रतिच्छेदन बिंदुओं पर चार तत्वों में यह गुण होता है कि ऊपरी-बाएँ और निचले दाएँ तत्वों का योग ([[मुख्य विकर्ण]] के पार) निचले-बाएँ और ऊपरी-दाएँ तत्वों ([[ प्रतिविकर्ण ]]के पार) के योग से कम या उसके बराबर होता है ।


यह मैट्रिक्स एक Monge सरणी है:
यह आव्यूह एक मोंगे सरणी है:
:<math>
:<math>
\begin{bmatrix}
\begin{bmatrix}
Line 31: Line 31:
36 & 33 & 19 & 21 & 6 \\
36 & 33 & 19 & 21 & 6 \\
75 & 66 & 51 & 53 & 34 \end{bmatrix}</math>
75 & 66 & 51 & 53 & 34 \end{bmatrix}</math>
उदाहरण के लिए, कॉलम 1 और 5 के साथ पंक्ति 2 और 4 का प्रतिच्छेदन लें।
उदाहरण के लिए, पंक्ति 1 और 5 के साथ पंक्ति 2 और 4 का प्रतिच्छेदन लें।
चार तत्व हैं:
 
चार तत्व निम्न हैं:
:<math>
:<math>
\begin{bmatrix}
\begin{bmatrix}
Line 44: Line 45:
==गुण==
==गुण==
*उपरोक्त परिभाषा कथन के समतुल्य है
*उपरोक्त परिभाषा कथन के समतुल्य है
:एक मैट्रिक्स एक स्पंज सरणी है यदि और केवल यदि <math>A[i,j] + A[i+1,j+1]\le A[i,j+1] + A[i+1,j]</math> सभी के लिए <math>1\le i < m</math> और <math>1\le j < n</math>.
:एक आव्यूह एक स्पंज सरणी है यदि और केवल यदि <math>A[i,j] + A[i+1,j+1]\le A[i,j+1] + A[i+1,j]</math> सभी के लिए <math>1\le i < m</math> और <math>1\le j < n</math> है।


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


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


== संदर्भ ==
== संदर्भ ==
{{Reflist}}
{{Reflist}}
* {{cite journal | title = Some problems around travelling salesmen, dart boards, and euro-coins | first1 = Vladimir G. | last1 = Deineko | first2 =  Gerhard J. | last2 = Woeginger | author2-link = Gerhard J. Woeginger | journal = Bulletin of the European Association for Theoretical Computer Science | publisher = [[European Association for Theoretical Computer Science|EATCS]] | volume = 90 |date=October 2006 | issn = 0252-9742 | pages = 43–52 | url = http://alexandria.tue.nl/openaccess/Metis211810.pdf | format = PDF }}
* {{cite journal | title = ट्रैवलिंग सेल्समैन, डार्ट बोर्ड और यूरो-सिक्के से जुड़ी कुछ समस्याएं | first1 = Vladimir G. | last1 = Deineko | first2 =  Gerhard J. | last2 = Woeginger | author2-link = गेरहार्ड जे. वोएजिंजर | journal = सैद्धांतिक कंप्यूटर विज्ञान के लिए यूरोपीय संघ का बुलेटिन | publisher = [[सैद्धांतिक कंप्यूटर विज्ञान के लिए यूरोपीय संघ|ईएटीसीएस]] | volume = 90 |date=October 2006 | issn = 0252-9742 | pages = 43–52 | url = http://alexandria.tue.nl/openaccess/Metis211810.pdf | format = PDF }}
[[Category: सैद्धांतिक कंप्यूटर विज्ञान]]  
[[Category: सैद्धांतिक कंप्यूटर विज्ञान]]  



Revision as of 09:13, 4 July 2023

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

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

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

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

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

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

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

17 + 7 = 24
23 + 11 = 34

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

गुण

  • उपरोक्त परिभाषा कथन के समतुल्य है
एक आव्यूह एक स्पंज सरणी है यदि और केवल यदि सभी के लिए और है।
  • मूल मोंगे सरणी से कुछ पंक्तियों और स्तंभों का चयन करके निर्मित कोई भी उपसरणी स्वयं एक मोंगे सरणी होगी।
  • मोंगे सरणियों के गैर-नकारात्मक गुणांक वाला कोई भी रैखिक संयोजन स्वयं एक मोंगे सरणी है।
  • मोंगे सरणियों की एक रोचक विशेषता यह है कि यदि आप प्रत्येक पंक्ति के सबसे बाईं ओर एक वृत्त के साथ चिह्नित करते हैं, तो आप पाएंगे कि आपके वृत्त दाईं ओर नीचे की ओर बढ़ते हैं; कहने का तात्पर्य यह है कि यदि , तब सभी के लिए है। सममित रूप से, यदि आप प्रत्येक पंक्ति के सबसे ऊपरी न्यूनतम को चिह्नित करते हैं, तो आपकी मंडलियां दाएं और नीचे की ओर प्रगति करेंगी। पंक्ति और स्तंभ मैक्सिमा विपरीत दिशा में चलते हैं: ऊपर से दाईं ओर और नीचे से बाईं ओर।
  • शक्तिहीन मोंगे सरणियों की धारणा प्रस्तावित की गई है; एक शक्तिहीन मोंगे सरणी एक वर्ग n-by-n आव्यूह है जो सभी के लिए मोंगे विशेषता को संतुष्ट करती है।
  • प्रत्येक मोंगे सरणी पूरी तरह से एकरस है, जिसका अर्थ है कि इसकी पंक्ति न्यूनतम स्तंभों के गैर-घटते अनुक्रम में होती है, और यह कि प्रत्येक उपसरणी के लिए समान गुण सत्य है। यह विशेषता स्मॉक कलन विधि का उपयोग करके पंक्ति मिनिमा को शीघ्रता से ढूंढने की अनुमति देती है।
  • मोन्ज आव्यूह दो अलग-अलग चरों के उपप्रतिरूपक फलन का दूसरा नाम है। संक्षेप में, A एक मोंगे आव्यूह है यदि और केवल यदि A[i,j] चर i,j का एक उपप्रतिरूपक फलन है।

अनुप्रयोग

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

संदर्भ

  1. Burkard, Rainer E.; Klinz, Bettina; Rudolf, Rüdiger (1996). "Perspectives of Monge properties in optimization". Discrete Applied Mathematics. ELSEVIER. 70 (2): 95–96. doi:10.1016/0166-218x(95)00103-x.