المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۵:سوال ۸

سوال ۸

در جمعی $n$ نفر حضور دارند. بعضی از این افراد همدیگر را می‌شناسند. فرض کنید که آشنایی یک رابطه‌ی دوطرفه است؛ یعنی اگر $a$ ٬$b$ را بشناسد، $b$ نیز $a$ را می‌شناسد. فرض کنید که هر نفر در این جمع حداکثر با $d$ نفر دیگر آشناست.

اگر $d=k+l+1$ باشد، می‌خواهیم این افراد را به دو گروه $A$ و $B$ تقسیم کنیم به‌ طوری‌ که هر یک از اعضای گروه $A$ حداکثر $k$ نفر از دیگر اعضای این گروه را بشناسد و هر یک از اعضای گروه $B$ هم با حداکثر $l$ نفر از دیگر اعضای این گروه آشنا باشد.

برای این منظور الگوریتم زیر پیشنهاد شده است:

ابتدا یک گروه‌بندی دل خواه $(A,B)$ را در نظر می‌گیریم. سپس در هر مرحله این کار را انجام می‌دهیم: اگر گروه‌بندی $(A,B)$ دارای شرایط مسأله بود، کار تمام شده است. درغیر این‌صورت یا یک نفر در $A$ وجود دارد که با بیش از $k$ نفر از اعضای گروهش آشنا باشد و یا یک نفر در گروه $B$ وجود دارد که با بیش از $l$ نفر از اعضای گروهش آشنا باشد. در هر یک از این دو حالت فرد مزبور را به گروه دیگر منتقل می‌کنیم.

ثابت کنید که این الگوریتم همواره به جواب می‌رسد.


ابزار صفحه