حل سؤال گراف و درجه رأس؛ تشخیص دام شمارش یال‌ها
حل سؤال گراف و درجه رأس با شمردن یال‌های متصل به هر رأس انجام می‌شود؛ مهم‌ترین دام این است که یال حلقه‌ای را دو بار در درجه همان رأس حساب کنیم و یال معمولی را فقط یک بار برای هر سر بشماریم.
حل سؤال گراف و درجه رأس؛ از کجا شروع کنیم؟
درجه یک رأس تعداد دفعاتی است که یال‌ها به آن رأس برخورد می‌کنند. در گراف بدون حلقه، هر یال میان دو رأس، درجه هر دو سر را یک واحد افزایش می‌دهد؛ بنابراین مجموع درجه همه رأس‌ها برابر دو برابر تعداد یال‌هاست. در گرافی که حلقه دارد، همان حلقه دو بار به درجه رأس خود اضافه می‌شود. این تفاوت، مبنای تشخیص بسیاری از گزینه‌های گمراه‌کننده است.
روش گام‌به‌گام
- رأس مورد سؤال را مشخص کنید و فقط یال‌هایی را بررسی کنید که یکی از دو سرشان به آن رأس می‌رسد؛ یال‌های دور از رأس در درجه آن نقشی ندارند.
- یال معمولی میان دو رأس متفاوت را برای هر یک از دو سر، یک برخورد حساب کنید؛ طول یال یا شکل خمیده آن اهمیتی ندارد.
- اگر یالی از رأس به خودش برگشته است، آن را دو برخورد بشمارید، چون یال حلقه‌ای هنگام ورود و خروج به همان رأس متصل است.
- برای کنترل شمارش، درجه همه رأس‌ها را جمع کنید و نتیجه را با دو برابر تعداد یال‌ها مقایسه کنید؛ اگر برابر نبود، یالی جا افتاده یا حلقه‌ای یک‌بار شمرده شده است.
- در سؤال‌های دارای درجه‌های داده‌شده، به‌جای شمردن دوباره شکل، از رابطه مجموع درجه‌ها برابر ۲ برابر تعداد یال‌ها استفاده کنید.
- اگر گزینه‌ای تعداد یال‌ها را از مجموع درجه‌ها به‌دست می‌آورد، تقسیم بر دو را فقط پس از درنظرگرفتن اثر دوبرابری حلقه‌ها انجام دهید.
گرافی با رأس‌های A، B، C و D را در نظر بگیرید که یال‌های AB، AC، BC، CD و یک حلقه روی D دارد. درجه A برابر ۲ است، چون AB و AC به آن می‌رسند. درجه B برابر ۲ و درجه C برابر ۳ است؛ C به A، B و D متصل است. درجه D برابر ۳ است، چون CD یک برخورد و حلقه روی D دو برخورد دارد. مجموع درجه‌ها ۱۰ و دو برابر تعداد پنج یال نیز ۱۰ است؛ پس شمارش سازگار است.
چطور این مبحث را مرور کنیم؟
برای بازبینی پاسخ، ابتدا درجه هر رأس را جداگانه بنویسید، سپس حلقه‌ها را دوباره کنترل کنید و در پایان مجموع درجه‌ها را با دو برابر تعداد یال‌ها بسنجید. در مثال بالا، درجات ۲، ۲، ۳ و ۳ هستند و جمع آن‌ها ۱۰ می‌شود؛ این کنترل نشان می‌دهد حلقه D دوبار محاسبه شده است.
اشتباه رایج این است که حلقه روی یک رأس را یک یال و یک برخورد بدانیم. حلقه از نظر تعداد یال‌ها یک مورد است، اما از نظر درجه رأس دو برخورد ایجاد می‌کند. اشتباه دیگر، شمردن تعداد یال‌های کل گراف به‌جای یال‌های متصل به رأس خواسته‌شده است.
جمع‌بندی
برای حل سؤال گراف و درجه رأس، ابتدا برخورد یال‌ها با رأس را بشمارید و حلقه را دو بار حساب کنید. سپس با آزمون مجموع درجه‌ها، برابر بودن آن با دو برابر تعداد یال‌ها را کنترل کنید؛ این روش هم پاسخ را پیدا می‌کند و هم دام شمارش ناقص را آشکار می‌سازد.
مطالعه مطلب آموزشی مرتبط ←