مشبکهٔ ‎$k \times k$‎ یک جدول ‎$k^2$‎ گره‌ای است که هر گرهِ آن به چهار گره بالا، پایین، چپ و راستش در صورت وجود متصل است.

برای هر جایگشتِ گره‌های مشبکه، عرضِ برشِ جایگشت به این صورت تعریف می‌شود: اگر همهٔ گره‌ها در ابتدا سفید باشند و یکی یکی با ترتیبِ جایگشتِ مورد نظر شروع به سیاه کردن آن‌ها کنیم، در هرمرحله تعداد یال‌های میان گره‌های سفید و سیاه را در نظر بگیرید. بیش‌ترین تعدادِ این یال‌ها را عرض برشِ آن جایگشت می‌گوییم. حال برای کل مشبکه، عرضِ برشی به این صورت تعریف می‌شود: مقدار کمینهٔ عرضِ برش جایگشت‌های مختلف. از میان تمامی ‎$k^2!$‎ جایگشت ممکن، جایگشتی که کوچک‌ترین عرض برش را دارد، مقدار عرض برشی کل مشبکه را ایجاد می‌کند.

حال با توجه به تعاریف بالا به سؤالات زیر پاسخ دهید:

1. برای مشبکهٔ‎ ‎$k \times k$، ‎($k \ge 3$)‎‎ثابت کنید عرض برشی کوچک‌تر و یا مساوی ‎$k+1$‎ است.
2. برای مشبکهٔ $3 \times 3$‎ (شامل ‎ ۹گره و ۱۲ یال دارد) عرض برشی را حساب کنید.
3. برای مشبکهٔ ‎$33 \times 33$‎ ثابت کنید عرض برشی برابر ‎$34$‎ است.

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