یک ماتریس $A=\{a[i,j]\}$ از اعداد حقیقی با اندازه‌ی $m\times n$ را ماتریس $Monge$ می‌گوییم اگر به ازای همه‌ی مقادیر $i$، $j$، $k$ و $l$ که $1\leq i<k\leq m$ و $1\leq j < l \leq n$ داشته باشیم:

$$a[i,j]+a[k,l]\leq a[i,l] + a[k,j]$$

مثال: ماتریس زیر $Monge$ است:

$$\begin{matrix} 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{matrix}$$

الف) اثبات کنید شرط لازم و کافی که یک ماتریس $Monge$ باشد این است که برای همه‌ی $i=1,2,...,m-1$ و $j=1,2,...,n-1$ داشته باشیم:

$$a[i,j]+a[i+1,j+1]\leq a[i,j+1]+a[i+1,j]$$

ب) با فرض داشتن $A$، یک الگوریتم کارا (از مرتبه‌ی نزدیک به $O(m+nlogm)$ ) برای تشخیص $Monge$ بودن $A$ ارائه دهید و آن را اثبات و تحلیل کنید.

• سوال بعد
• سوال قبل