گراف جهت‌دار و حل مسأله با گراف

این کارگاه تکمیلی است و در کتاب‌های درسی افغانستان نیامده است. گراف یک مدل ساده است؛ رأس‌ها آدم‌ها، شهرها یا تیم‌ها هستند و یال‌ها رابطه‌ها (دوستی، جاده، مسابقه). اگر رابطه جهت داشته باشد («الف از ب جلو زد»)، یال را با تیر می‌کشیم و گراف جهت‌دار می‌شود. هر رأس تعدادی تیر خروجی و تعدادی تیر ورودی دارد.

مسأله‌های کلاسیک: دست‌دادن در جمع n نفر (هر کس با هر کس یک بار) و بازی‌های یک لیگ (هر تیم با هر تیم دیگر بازی می‌کند). مجموع درجه‌ها دو برابر تعداد یال‌هاست؛ پس تعداد یال‌ها نصف مجموع درجه‌هاست. برای n رأس که همه به هم وصل‌اند، تعداد یال‌ها n·(n − ۱) ÷ ۲ است.

اشتباه رایج این است که هر یال را دو بار بشماریم. اشتباه دیگر قاطی کردن تیر‌های خروجی و ورودی است. مسألهٔ مسیر را با شمردن یال‌های کوتاه‌ترین مسیر حل می‌کنیم.