المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۱:گراف:سوال ۵

تکامل

یک گراف دو بخشی جهت دار ناکامل داریم. این گراف، شامل دو بخش $A$ و $B$ است که بخش $A$، $a$ راس و $B$، $b$ راس را شامل می‌گردند. $p$ راس از رئوس $A$ را در نظر گرفته‌ایم و از هر کدام، دقیقا یک یال جهت‌دار به یکی از رئوس $B$ کشیده‌ایم. توجه کنید که ابتدای هر یک از این یال‌ها در $A$ است و چند یال می‌توانند انتهایی یکسان داشته باشند.

می‌خواهیم از هر یک از رئوس $B$ دقیقا یک یال جهت‌دار بکشیم که انتهای این یال‌ها در $A$ باشد. هم‌چنین می‌خواهیم این کار را به گونه‌ای انجام دهیم که گراف نهایی، دور جهت‌دار (به طول ۲ یا بیش‌تر) نداشته باشد.

با فرض ترتیب‌دار بودن رئوس، به چند روش می‌توان این کار را انجام داد؟

پاسخ


ابزار صفحه