جلسهی 22: گراف: نقطهها و خطها Graphs: Points and Lines
گراف یعنی چند نقطه (رأس) و خطهایی بینشان (یال): دوستیها، جادهها، مسابقهها. درجهی رأس، قانون دست دادن (جمع درجهها دو برابر یالهاست) و گرافِ کامل.
در این جلسه یاد میگیری
- یک موقعیت را با گراف نشان میدهی و درجهی هر رأس را میشماری.
- قانون دست دادن را به کار میبری: جمع درجهها = ۲ × تعداد یالها.
- میدانی تعداد رأسهای درجهفرد همیشه زوج است.
درس
گراف یک ابزار ساده برای خیلی از سؤالهای المپیاد است: هر آدم (یا شهر، یا تیم) یک نقطه است که به آن «رأس» میگوییم، و هر رابطه (دوستی، جاده، بازی) یک خط بین دو رأس که به آن «یال» میگوییم. «درجه»ی یک رأس یعنی تعداد یالهایی که به آن وصلاند (مثلاً تعداد دوستانِ یک نفر).
نقطهها را به هم وصل کن تا درجهها به ترتیب ۳، ۳، ۳، ۳، ۲ شوند. حواست به «جمعِ درجهها» و «تعداد یالها» باشد.
قانون دست دادن: هر یال دو سر دارد و به درجهی هر دو سرش یکی اضافه میکند. پس جمعِ درجهها همیشه دقیقاً ۲ برابرِ تعداد یالهاست و زوج است. نتیجه: تعداد رأسهایی که درجهشان فرد است همیشه زوج است.
حالا این یکی را امتحان کن: ۵ نقطه که درجهی همه ۳ باشد. جمعشان ۱۵ میشد که فرد است. پس غیرممکن است، هر چقدر هم تلاش کنی!
گرافِ کامل: n رأس که هر دو تایشان به هم وصلاند (مثل دست دادنِ همه با همه). هر رأس درجهی n − ۱ دارد و تعداد یالها C(n، ۲) = n(n − ۱) ÷ ۲ است. همین را با قانون دست دادن هم میشود دید: n × (n − ۱) ÷ ۲.
اشتباه رایج: شمردنِ هر یال دو بار (یک بار از هر سر). اگر درجهها را جمع زدی، یادت باشد بر ۲ تقسیم کنی.
چالشها
- Sum of Degrees (آسان)
- Seven Handshakes Each (آسان)
- Ten Friends (متوسط)
- Everyone Connected (متوسط)
- Leaving the Party (سخت)
- At Least Three Each (سخت)
← جلسهی 21: آزمونک بازی و الگوریتم جلسهی 23: مسیر، دور و کشیدن با یک خط →