گراف جهت‌دار و حل مسئله با گراف
گراف جهت‌دار را بخوان، دست‌دادن‌ها و بازی‌های یک لیگ را بشمار و با تبدیل مسئله به گراف، کوتاه‌ترین مسیر را پیدا کن.
📖 از اینجا شروع کن: گام‌های «درس» را به ترتیب بخوان (۱، ۲، ۳ …) و به هر پرسش جواب بده. بعد با «تمرین» ادامه بده.
- روسیه: کلاس ۷
راهنما
این کارگاه با فصل «گراف و مدل‌سازی» ریاضیات گسسته (پایهٔ دوازدهم) ارتباط دارد. گراف یک مدل ساده است؛ رأس‌ها آدم‌ها، شهرها یا تیم‌ها هستند و یال‌ها رابطه‌ها (دوستی، جاده، مسابقه). اگر رابطه جهت داشته باشد («الف از ب جلو زد»)، یال را با پیکان می‌کشیم و گراف جهت‌دار می‌شود. هر رأس تعدادی پیکان خروجی و تعدادی پیکان ورودی دارد.
مسئله‌های کلاسیک: دست‌دادن در جمع n نفر (هر کس با هر کس یک بار) و بازی‌های یک لیگ (هر تیم با هر تیم دیگر بازی می‌کند). مجموع درجه‌ها دو برابر تعداد یال‌هاست؛ پس تعداد یال‌ها نصف مجموع درجه‌هاست. برای n رأس که همه به هم وصل‌اند، تعداد یال‌ها n·(n − ۱) ÷ ۲ است.
اشتباه رایج این است که هر یال را دو بار بشماریم. اشتباه دیگر قاطی کردن پیکان‌های خروجی و ورودی است. مسئلهٔ مسیر را با شمردن یال‌های کوتاه‌ترین مسیر حل می‌کنیم.