فهرست مندرجات
سوالات ۱۶ تا ۱۸
فرض کنید $G$ یک گراف باشد که روی هر یال آن یکی از دو عدد $1$ و $-1$ نوشته شده است. در هر مرحله می‌توان یک رأس از گراف در نظر گرفت و عدد تمام یال‌های متصل به آن را قرینه کرد. کمینه‌ی تعداد یال‌های با عدد $-1$ را که می‌توان با انجام تعدادی مرحله به آن رسید، $f(G)$ می‌نامیم. برای مثال در گراف زیر مقدار تابع $f$ برابر ۰ است.
بیشینه‌ی مقدار $f(G)$ را به ازای تمام مقادیر اولیه‌ی ممکن برای یال‌ها، $h(G)$ در نظر می‌گیریم. برای مثال در گراف زیر مقدار $h$ برابر ۱ است:
همان‌طور که در مثال بالا می‌بینید، ورودی تابع $f$ گرافی با یال‌های مقداردهی شده و ورودی تابع $h$ گرافی با یال‌های مقداردهی نشده است.
سوال ۱۶
مقدار $h$ را برای گراف زیر بیابید:
- $0$
- $1$
- $2$
- $3$
- $4$
پاسخ
گزینه (۳) درست است.
گراف شامل دو دور مجزایال است. هر دور اگر در ابتدا شامل تعداد فردی یال $-1$ باشد، هم‌واره تعداد فردی یال $-1$ خواهد داشت. پس پاسخ حداقل برابر ۲ است. هم‌چنین می‌توان تمام یال‌های مسیر ۴-رأسی پایین را ۱ کرد و سپس اگر در یال‌های متصل به رأس بالا بیش از دو یال $-1$ وجود داشت، با انتخاب رأس بالا تعداد یال‌های $-1$ گراف را حداکثر ۲ کرد.
سوال ۱۷
مقدار $h$ را برای گراف زیر بیابید:
- $0$
- $1$
- $2$
- $3$
- $4$
پاسخ
گزینه (۳) درست است.
فرض کنید مقداردهی اولیه به شکل زیر باشد (فقط اعداد $-1$ نوشته شده است):
ادعا می‌کنیم به ازای مقداردهی بالا مقدار $f$ از ۲ کم‌تر نیست. فرض کنید از ۲ کم‌تر باشد. به مانند استدلال سوال قبل این مقداردهی شامل یک دور با تعداد فردی $-1$ است. پس نمی‌تواند مقدار $f$ برابر ۰ باشد. هم‌چنین اگر بخواهد این مقدار برابر ۱ شود باید تنها یال $-1$، یال بین رئوس ۲ و ۵ باشد؛ زیرا هر یک از دورهای $1, 2, 4, 5$ و $2, 3, 5, 6$ شامل حداقل یک یال $-1$ خواهند بود. این حالت نیز قابل دست‌یابی نیست؛ زیرا انتخاب شدن و نشدن رأس‌ها یک‌تا تعیین می‌شود و مشاهده می‌کنیم نمی‌توان به این حالت رسید.
از طرفی به ازای هر مقداردهی اولیه می‌توان کاری کرد که حداکثر ۲ یال $-1$ داشته باشیم. پس پاسخ برابر ۲ است.
سوال ۱۸
کدام گزاره‌های زیر درست هستند؟
- الف) مقدار $h$ در هر گراف از بیشینه‌ی تعداد دورهای یال‌مجزا کم‌تر نیست (به مجموعه‌ای از دورها، دورهای یال‌مجزا می‌گوییم اگر هر یال از گراف در حداکثر یکی از دورهای آن مجموعه آمده باشد).
- ب) مقدار $h$ در هر گراف از بیشینه‌ی تعداد دورهای یال‌مجزا بیش‌تر نیست.
- ج) فرض کنید $G$ یک گراف با یک مقداردهی اولیه باشد که $f(G)=0$. اگر $G$ دارای $k$ مؤلفه باشد، دقیقاً $2^k$ روش وجود دارد که در آن هر رأس انتخاب شود یا نشود و در انتها عدد روی تمام یال‌ها $1$ شوند.
- الف
- الف و ب
- ب و ج
- الف و ج
- الف و ب و ج
پاسخ
گزینه (۴) درست است.
گزاره‌‌ب با مثالی که در سوال قبلی آمده متناقض است.
گزاره‌های الف و ج درست هستند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
