المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۰:سوال ۲۱

سوال ۲۱

درجه‌ی یک رأس در گراف برابر تعداد یال‌هایی از گراف است که به آن متصل هستند. در گراف مقابل به هر رأس، عددی برابر مجموع درجه‌های همسایه‌های آن رأس نسبت می‌دهیم. فرض کنید مجموع این اعداد برابر ‎$A$‎ شود. در گام بعدی روی هر یال یک رأس جدید اضافه می‌کنیم و دوباره برای هر رأس، همان عمل را انجام می‌دهیم. مجموع اعداد جدید را ‎$B$‎ می‌نامیم. ‎$B-A$‎ چند است؟

  1. ۳۰
  2. ۶۰
  3. ۶۲
  4. ۱۲۰
  5. ۱۲۴

پاسخ

گزینه (؟) درست است.

درجه‌ی هر راس از گراف به تعداد درجه‌ی آن راس در نوشتن $A$ به کار می‌رود بنابراین اگر درجه‌ی رئوس را $a_2 ، a_1$،…،$a_n$ در نظر بگیریم آن‌گاه خواهیم داشت:

$$A=a_1 \times a_1+a_2 \times a_2+...+a_n \times a_n= \sum {a_i}^2$$

به همین ترتیب معلوم می‌شود که:

$$B= \sum {a_i}^2+(\underbrace{2^2+2^2+...+2^2}_{29تا}$$

$$ \Rightarrow B-A=29\times 4=116$$

یادآوری می‌شود که تعداد یال‌های گراف داده شده برابر ۲۹ می‌باشد. همان‌طور که دیده می‌شود عدد به‌دست آمده در هیچ‌یک از گزینه‌ها نیامده است.


ابزار صفحه