मोंगे सरणी: Difference between revisions
(Created page with "{{refimprove|date=September 2012}} कंप्यूटर विज्ञान पर लागू गणित में, मोंगे ऐरे, या मों...") |
(text) |
||
Line 1: | Line 1: | ||
{{refimprove|date=September 2012}} | {{refimprove|date=September 2012}} | ||
[[कंप्यूटर विज्ञान]] पर लागू गणित में, मोंगे | [[कंप्यूटर विज्ञान]] पर लागू गणित में, '''मोंगे सरणी''', या मोंगे आव्यूह, गणितीय वस्तुएं हैं जिनका नाम उनके खोजकर्ता, फ्रांसीसी गणितज्ञ [[गैसपार्ड मोंगे]] के नाम पर रखा गया है। | ||
एक ''m''-by-''n'' [[मैट्रिक्स (गणित)]] को | एक ''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 उप-आव्यूह) की किन्हीं दो पंक्तियों और दो स्तंभों के लिए प्रतिच्छेदन बिंदुओं पर चार तत्वों में यह गुण होता है कि ऊपरी-बाएँ और निचले दाएँ तत्वों का योग ([[मुख्य विकर्ण]] के पार) निचले-बाएँ और ऊपरी-दाएँ तत्वों ([[ प्रतिविकर्ण ]]के पार) के योग से कम या उसके बराबर होता है । | ||
यह | यह आव्यूह एक मोंगे सरणी है: | ||
:<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 का प्रतिच्छेदन लें। | ||
चार तत्व हैं: | |||
चार तत्व निम्न हैं: | |||
:<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>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> है। सममित रूप से, यदि आप प्रत्येक पंक्ति के सबसे ऊपरी न्यूनतम को चिह्नित करते हैं, तो आपकी मंडलियां दाएं और नीचे की ओर प्रगति करेंगी। पंक्ति और स्तंभ मैक्सिमा विपरीत दिशा में चलते हैं: ऊपर से दाईं ओर और नीचे से बाईं ओर। | ||
* | *शक्तिहीन मोंगे सरणियों की धारणा प्रस्तावित की गई है; एक शक्तिहीन मोंगे सरणी एक वर्ग 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> को संतुष्ट करती है। | ||
* प्रत्येक | * प्रत्येक मोंगे सरणी पूरी तरह से एकरस है, जिसका अर्थ है कि इसकी पंक्ति न्यूनतम स्तंभों के गैर-घटते अनुक्रम में होती है, और यह कि प्रत्येक उपसरणी के लिए समान गुण सत्य है। यह विशेषता स्मॉक कलन विधि का उपयोग करके पंक्ति मिनिमा को शीघ्रता से ढूंढने की अनुमति देती है। | ||
*मोन्ज | *मोन्ज आव्यूह दो अलग-अलग चरों के [[सुपरमॉड्यूलर फ़ंक्शन|उपप्रतिरूपक फलन]] का दूसरा नाम है। संक्षेप में, A एक मोंगे आव्यूह है यदि और केवल यदि A[i,j] चर i,j का एक उपप्रतिरूपक फलन है। | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
*एक वर्ग | *एक वर्ग मोंगे आव्यूह जो अपने मुख्य विकर्ण के बारे में भी सममित है, उसे [[सपनिक मैट्रिक्स|सपनिक आव्यूह]] कहा जाता है ([[फ्रेड सुपनिक]] के बाद); इस प्रकार के आव्यूह में टीएसपी के अनुप्रयोग होते हैं (अर्थात्, जब [[दूरी मैट्रिक्स|दूरी आव्यूह]] को सुपनिक आव्यूह के रूप में लिखा जा सकता है तो समस्या आसान समाधान स्वीकार करती है)। सुपनिक आव्यूह का कोई भी रैखिक संयोजन स्वयं एक सुपनिक आव्यूह है। | ||
== संदर्भ == | == संदर्भ == | ||
{{Reflist}} | {{Reflist}} | ||
* {{cite journal | title = | * {{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
This article needs additional citations for verification. (September 2012) (Learn how and when to remove this template message) |
कंप्यूटर विज्ञान पर लागू गणित में, मोंगे सरणी, या मोंगे आव्यूह, गणितीय वस्तुएं हैं जिनका नाम उनके खोजकर्ता, फ्रांसीसी गणितज्ञ गैसपार्ड मोंगे के नाम पर रखा गया है।
एक 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 का एक उपप्रतिरूपक फलन है।
अनुप्रयोग
- एक वर्ग मोंगे आव्यूह जो अपने मुख्य विकर्ण के बारे में भी सममित है, उसे सपनिक आव्यूह कहा जाता है (फ्रेड सुपनिक के बाद); इस प्रकार के आव्यूह में टीएसपी के अनुप्रयोग होते हैं (अर्थात्, जब दूरी आव्यूह को सुपनिक आव्यूह के रूप में लिखा जा सकता है तो समस्या आसान समाधान स्वीकार करती है)। सुपनिक आव्यूह का कोई भी रैखिक संयोजन स्वयं एक सुपनिक आव्यूह है।
संदर्भ
- ↑ 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.
- Deineko, Vladimir G.; Woeginger, Gerhard J. (October 2006). "ट्रैवलिंग सेल्समैन, डार्ट बोर्ड और यूरो-सिक्के से जुड़ी कुछ समस्याएं" (PDF). सैद्धांतिक कंप्यूटर विज्ञान के लिए यूरोपीय संघ का बुलेटिन. ईएटीसीएस. 90: 43–52. ISSN 0252-9742.