سوال ۷

شکل زیر از ۳۱ رأس (نقطه) متمایز و ۳۰ یال (پارەخط) ساخته شده است.

گراف

فاصله‌ی دو رأس برابر کمترین تعداد یال‌های مورد نیاز برای رفتن از یکی به دیگری است. فاصله‌ی چند جفت رأس در این شکل برابر ۵ است؟ دقت کنید برای دو رأس $a$ و $b$، جفت $(a,b)$ و $(b,a)$ یکسان محسوب می‌شوند.

  1. ۱۶
  2. ۹۶
  3. ۱۲۸
  4. ۶۴
  5. ۸۰

راهنمایی

ساختار شکل داده شده را از بالا به پایین به صورت لایه لایه در نظر بگیرید (لایه اول دارای ۱ رأس، لایه دوم دارای ۲ رأس،…). برای جفت رأس های مورد نظر حالت‌های قرار گرفتن در لایه‌های مختلف را بررسی کنید.