المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

یک تیم، شش نفر با شمارە های ۱ تا ۶ دارد. می دانیم:

  • سه نفر از اعضای تیم، هر کدام، یک دوست درون تیم دارند.
  • دو نفر از اعضای تیم، هر کدام، دو دوست درون تیم دارند.
  • یک نفر از اعضای تیم، سه دوست درون تیم دارد.

دوستی های بین افراد تیم، دوطرفه است (یعنی اگر $A$ دوستِ $B$ باشد، $B$ نیز دوستِ $A$ است). چند حالت مختلف از دوستی این افراد با شرایط گفته شده وجود دارد؟ دو حالت را متفاوت گوییم، اگر دو نفر مانند $X$ و $Y$ وجود داشته باشند که در یک حالت، دوست باشند و در حالت دیگر، دوست نباشند.

  1. ۷۲۰
  2. ۱۰۰۰
  3. ۹۰۰
  4. ۳۶۰
  5. ۱۸۰

راهنمایی

گراف دوستی های این تیم را در نظر بگیرید(منظور گرافی است که راس های آن متناظر با افراد تیم هستند و بین دو راس یال وجود دارد اگر و تنها اگر افراد متناظر با آن دو راس با هم دوست باشند).
چند کلاس همریختی متفاوت برای این گراف وجود دارد؟

راهنمایی

سه کلاس همریختی متفاوت برای این گراف وجود دارد!
به ازای هر کلاس همریختی، تعداد روش های متفاوت نسبت دادن اعداد ۱ تا ۶ به راس های آن را بیابید.


ابزار صفحه