====== سوال ۱۰ ======


چند ضلعی ساده‌ی (بدون حفره‌) $P$ را شبکه‌ای گوییم، اگر رئوس آن مختصات صحیح داشته باشند و اضلاع آن افقی یا عمودی باشند. به وضوح $P$ شامل تعدادی مربع واحد است. حال گرافی به این صورت از روی $P$ می‌سازیم:

به ازای هر مربع واحد از $P$، یک راس قرار می‌دهیم و دو راس را با یال به هم وصل می‌کنیم اگر خانه‌های متناظر، مجاور ضلعی باشند. به گراف حاصل $G_p$ می‌گوییم.

  - ثابت کنید $G_p$ گرافی دو بخشی است.
  - گرافی دو بخشی و همبند مانند $G$ مثال بزنید که درجه هر راس از آن حداکثر ۳ باشد، ولی چند ضلعی شبکه‌ای $P$ موجود نباشد به طوری که: $G=G_P$.
  - همه چندضلعی‌های شبکه‌ای مثل $P$ را بیابید که تعداد راس‌های یکی از بخش‌های $G_P$ بیش از سه برابر تعداد راس‌های بخش دیگر آن باشد.


  * [[سوال ۱۱|سوال بعد]]
  * [[سوال ۹|سوال قبل]]