Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:ترکیبیات:سوال ۱۰

سوال ۱۰

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

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

  1. ثابت کنید Gp گرافی دو بخشی است.
  2. گرافی دو بخشی و همبند مانند G مثال بزنید که درجه هر راس از آن حداکثر ۳ باشد، ولی چند ضلعی شبکه‌ای P موجود نباشد به طوری که: G=GP.
  3. همه چندضلعی‌های شبکه‌ای مثل P را بیابید که تعداد راس‌های یکی از بخش‌های GP بیش از سه برابر تعداد راس‌های بخش دیگر آن باشد.

ابزار صفحه