بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 22: گراف: نقطه‌ها و خط‌ها Graphs: Points and Lines

گراف یعنی چند نقطه (رأس) و خط‌هایی بینشان (یال): دوستی‌ها، جاده‌ها، مسابقه‌ها. درجه‌ی رأس، قانون دست دادن (جمع درجه‌ها دو برابر یال‌هاست) و گرافِ کامل.

در این جلسه یاد می‌گیری

درس

گراف یک ابزار ساده برای خیلی از سؤال‌های المپیاد است: هر آدم (یا شهر، یا تیم) یک نقطه است که به آن «رأس» می‌گوییم، و هر رابطه (دوستی، جاده، بازی) یک خط بین دو رأس که به آن «یال» می‌گوییم. «درجه»ی یک رأس یعنی تعداد یال‌هایی که به آن وصل‌اند (مثلاً تعداد دوستانِ یک نفر).

نقطه‌ها را به هم وصل کن تا درجه‌ها به ترتیب ۳، ۳، ۳، ۳، ۲ شوند. حواست به «جمعِ درجه‌ها» و «تعداد یال‌ها» باشد.

قانون دست دادن: هر یال دو سر دارد و به درجه‌ی هر دو سرش یکی اضافه می‌کند. پس جمعِ درجه‌ها همیشه دقیقاً ۲ برابرِ تعداد یال‌هاست و زوج است. نتیجه: تعداد رأس‌هایی که درجه‌شان فرد است همیشه زوج است.
حالا این یکی را امتحان کن: ۵ نقطه که درجه‌ی همه ۳ باشد. جمعشان ۱۵ می‌شد که فرد است. پس غیرممکن است، هر چقدر هم تلاش کنی!

گرافِ کامل: n رأس که هر دو تایشان به هم وصل‌اند (مثل دست دادنِ همه با همه). هر رأس درجه‌ی ⁦n − ۱⁩ دارد و تعداد یال‌ها C(n، ۲) = n(n − ۱) ÷ ۲ است. همین را با قانون دست دادن هم می‌شود دید: ⁦n × (n − ۱) ÷ ۲⁩.
اشتباه رایج: شمردنِ هر یال دو بار (یک بار از هر سر). اگر درجه‌ها را جمع زدی، یادت باشد بر ۲ تقسیم کنی.

چالش‌ها

  1. Sum of Degrees (آسان)
  2. Seven Handshakes Each (آسان)
  3. Ten Friends (متوسط)
  4. Everyone Connected (متوسط)
  5. Leaving the Party (سخت)
  6. At Least Three Each (سخت)

← جلسه‌ی 21: آزمونک بازی و الگوریتم جلسه‌ی 23: مسیر، دور و کشیدن با یک خط →