تعریف گراف شبکه‌ای $n\times n$: راس‌های گراف همهٰ‌ی زوج مرتب‌های به شکل $(i,j)$ است که $i$ و $j$ اعداد صحیح ۱ تا $n$ می‌باشند. (پس این گراف، $n\times n$ راس دارد). راس $(i,j)$ به راس‌های $(i+1,j)$، $(i-1,j)$، $(i,j+1)$ و $(i,j-1)$ در صورت وجود یال دارد.(پس درجه‌ی هر راس ۲،۳ و یا ۴ است.)

درخت $T$ بسازید به طوری که هر راس آن یک زیرمجموعه با اندازه‌ی حداکثر $n+1$ از راس‌های گراف شبکه‌ای $G$ را دارا باشد و دو خصوصیت زیر را نیز داشته باشد:

1. اگر بین دو راس گراف $G$ یک یال هست، این دو راس حداقل در مجموعه‌ی یکی از راس‌های $T$ باهم می‌آیند(دقت کنید که هر دو راسی از گراف $G$ که در مجموعه‌ی یکی از راس‌های $T$ می‌آیند، لزوما در $G$ به هم یال ندارند).
2. برای هر راس گراف $G$ مانند $v$، راس‌هایی از $T$ که $v$ را در مجموعه‌ی خود دارند تشکیل یک زیر گراف همبند بدهند.

توجه باید صحت روش ساخت خود را اثبات کنید.

• سوال بعد