فهرست مندرجات
سوالات ۱۹ و ۲۰
فرض کنید $G$ یک گراف ساده باشد. منظور از فاصله‌ی بین دو رأس در گراف، طول کوتاه‌ترین مسیر بین آن‌هاست. منظور از قطر یک گراف، بیشینه‌ی فاصله‌ی دوبه‌دوی میان رأس‌هاست. توجه کنید در یک گراف ناهم‌بند، قطر گراف $\infty$ است. به یک گراف قطر بحرانی گوییم، اگر با حذف هر یال از آن، قطر گراف زیاد شود. هم‌چنین به یک گراف قطر بحرانی معکوس گوییم، اگر با اضافه کردن یال بین هر دو رأس غیر همسایه، قطر گراف کم شود.
سوال ۱۹
تعداد گراف‌های 6 رأسی و 6 یالی را بیابید که قطر بحرانی و دوبه‌دو نایک‌ریخت باشند. (دو گراف را یک‌ریخت می‌نامیم اگر بتوان با نام‌گذاری مجدّد رأس‌های اولی، گرافی برابر با گراف دومی ساخت)
- $2$
- $3$
- $4$
- $5$
- $6$
پاسخ
گزینه (۲) درست است.
چنین گرافی همبند است و در نتیجه درختی است که یک یال به آن اضافه شده. کافیست که بر اساس اندازه‌ی دوری که در گراف است مسئله را تقسیم کنیم. در این صورت ۳ گراف این ویژگی را خواهند داشت (یکی دور به طول ۶، یکی دور به طول ۵ و دیگری دوری به طول ۳).
سوال ۲۰
تعداد گراف‌های هم‌بندِ غیرکامل 7 رأسی را بیابید که قطر بحرانی معکوس و دوبه‌دو نایک‌ریخت باشند.
- $8$
- $9$
- $10$
- $11$
- $7$
پاسخ
گزینه (۳) درست است.
کافیست که قطر فعلی گراف را در نظر بگیریم. در این صورت اگر راس‌ها را بر اساس فاصله از دو راس تقسیم‌بندی کنیم، راس‌های هم‌فاصله باید گرافی کامل را تشکیل دهند (در غیر این صورت با اضافه کردن یال قطر گراف کم نخواهد شد) و بین تمامی رئوس دو بخش مجاور یال هست. تنها نکته باقی‌مانده این است که بخش‌های اول و آخر (دو سر قطر) تنها شامل یک راس هستند (در غیر این صورت با اضافه کردن یالی بین یکی از آن‌ها و راسی در فاصله‌ی دو از از قطر، قطر گراف افزایش نخواهد یافت).
با این تفاسیر کافیست که تعداد اعضای هر بخش را تعیین کنیم تا گراف به‌صورت یکتا تعیین شود که با شمارشی ساده عدد ۱۰ به‌دست می‌آید.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
