المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۷:سوالات ۱۴ و ۱۵

سوالات ۱۴ و ۱۵

یک گراف ساده را سلطانی گوییم، اگر اختلاف درجه‌ی هیچ دو رأس آن برابر یک نباشد. برای مثال گراف زیر سلطانی نیست، زیرا هم رأس با درجه‌ی یک و هم رأس با درجه‌ی دو دارد: توجه کنید در یک گراف سلطانی، وجود دو رأس با درجه‌ی برابر مشکلی ندارد. برای مثال، گراف زیر سلطانی است:

سوال ۱۴

یک گراف ساده‌ی ۱۱ رأسی سلطانی داریم که کامل نیست. این گراف حداکثر چند یال دارد؟

  1. ۴۹
  2. ۵۳
  3. ۵۲
  4. ۴۵
  5. ۵۴

پاسخ

گزینه (۳) درست است.

اگر گراف تنها یک یا دو یال از $\binom{11}{2}$ یال موجود را نداشته باشد، هم رأس با درجه‌ی ۱۰ و هم رأس با درجه‌ی ۹ خواهد داشت. پس حداکثر $\binom{11}{2} - 3 = 52$ یال داریم. حال یک گراف کامل ۱۱ رأسی در نظر بگیرید که یک مثلث از یال‌های آن پاک شوند. این گراف ۳ رأس با درجه‌ی ۸ و ۸ رأس را درجه‌ی ۱۰ دارد که معتبر است.

سوال ۱۵

یک گراف ساده‌ی ۱۱ رأسی سلطانی داریم. در این گراف هیچ سه رأسی وجود ندارد که دو به دو به هم وصل باشند. این گراف حداکثر چند یال دارد؟

  1. ۲۶
  2. ۲۹
  3. ۲۸
  4. ۲۷
  5. ۳۰

پاسخ

گزینه (۳) درست است.

ابتدا ثابت می‌کنیم تعداد یال‌ها نمی‌تواند از ۲۸ بیش‌تر باشد. طبق قضیه‌ی منتل یک گراف $n$ رأسی فاقد مثلث، نمی‌تواند بیش از $\lfloor \frac{n^2}{4} \rfloor$ یال داشته باشد (اثبات این قضیه را می‌توانید در کتاب‌های گراف بیابید). دو حالت داریم:

  • گراف، دور به طول فرد دارد: فرض کنید طول کوچک‌ترین دور به طول فرد برابر $2l+1$ باشد. رأس‌های این دور، یالی به جز یال‌های خود دور به هم ندارند (زیرا در غیر این صورت دوری به طول کم‌تر و فرد خواهیم داشت). هر رأس خارج دور، حداکثر به $l$ رأس از دور وصل است (زیرا در غیر این صورت مثلث تشکیل می‌شود). $11-(2l+1)=10-2l$ رأس دیگر نیز حداکثر $\lfloor \frac{(10-2l)^2}{4} \rfloor = \frac{(5-l)^2}{4}$ یال بین خود دارند. پس گراف دارای حداکثر $$(2l+1)+(10-2l)\times l + (5-l)^2$$ یال است. مقدار $l$ می‌تواند ۱، ۲، … یا ۵ باشد. با گذاشتن این مقادیر در عبارت بالا، حداکثر ۲۷ یال خواهیم داشت.
  • گراف دور به طول فرد ندارد: پس گراف دوبخشی است. اگر یک بخش آن حداکثر چهار رأس داشته باشد، حداکثر ۲۸ یال خواهیم داشت. حال گراف دوبخشی کامل با بخش‌های پنج و شش رأسی را در نظر بگیرید. با حذف حداکثر یک یال از این گراف، هم رأس با درجه‌ی پنج و هم رأس با درجه‌ی شش خواهیم داشت؛ پس در هر صورت گراف ما دست کم ۲۸ یال دارد.

ابزار صفحه