سلطان به تازگی شهردار خوشوآباد شده و می‌خواهد به روان شدن ترافیک شهر کمک کند. استراتژی او، یک‌طرفه کردن خیابان‌هاست. از طرفی او دوست ندارد با این کار، فاصله‌ی قسمت‌های مختلف شهر از هم خیلی زیاد شود. در هر سوال، گراف خیابان‌ها و تقاطع‌های یک محله داده می‌شود (رأس‌های گراف، تقاطع‌ها و یال‌های آن، خیابان‌های محله هستند) و از شما در مورد یک‌طرفه کردن خیابان‌های آن پرسشی صورت خواهد گرفت. در هر سه سوال، رأس‌های (تقاطع‌های) گراف را متمایز در نظر بگیرید.

محله‌ی کوچک رامتینک در این شهر گرافی به شکل زیر دارد:

سلطان می‌خواهد تمام خیابان‌های این محله را یک‌طرفه کند، طوری که به ازای هر زوج مرتب $(X, Y)$ از تقاطع‌ها، بتوانیم با طی کردن حداکثر چهار خیابان از $X$ به $Y$ برسیم. به چند طریق این کار ممکن است؟

1. 2
2. 8
3. 4
4. 6
5. 0

محله‌ی قدیمی میرزامحمد خان گرافی به شکل زیر دارد:

سلطان می‌خواهد تمام خیابان‌های این محله را یک‌طرفه کند، طوری که به ازای هر زوج مرتب $(X, Y)$ از تقاطع‌ها، بتوانیم با طی کردن حداکثر سه خیابان از $X$ به $Y$ برسیم. به چند طریق این کار ممکن است؟

1. 32
2. 4
3. 24
4. 12
5. 0

محله‌ی زیبای پارساییان گرافی به شکل زیر دارد:

در این سوال بر خلاف دو سوال قبل، سلطان نمی‌خواهد تمام خیابان‌ها را یک‌طرفه کند، زیرا چهار خیابان مشخص شده با خط‌چین به اندازه‌ی کافی عریض هستند و نیازی به یک‌طرفه شدن آن‌ها نیست. سلطان به چند طریق می‌تواند تمام ۱۲ خیابان دیگر را یک‌طرفه کند، طوری که به ازای هر زوج مرتب $(X, Y)$ از تقاطع‌ها، بتوانیم با طی کردن حداکثر پنج خیابان از $X$ به $Y$ برسیم؟

1. 0
2. 4
3. 2
4. 12
5. 96

• سوال قبل