====== سوال ۸ ======


یال‌های یک گراف با تعدادی رنگ، رنگ‌آمیزی شده‌اند. ‎«عدد تنوّع»‎ برای یک مسیر، تعداد رنگ‌های موجود در یال‌های آن مسیر است. 
تعداد بخش‌های یک رنگ مانند ‎$c$‎ به این صورت به دست می‌آید که صرفاً یال‌های به رنگ ‎$c$‎ را در گراف درنظرمی‌گیریم و تعداد مؤلفه‌هایی 
از این گراف حاصل را که حداقل یک یال دارند، تعداد بخش‌های این رنگ می‌نامیم. 
برای حل قسمت ب می‌توانید قسمت الف را درست فرض کنید.
  * الف) الگوریتمی چندجمله‌ای ارائه کنید که اگر در گراف ما تعداد بخش‌های هر رنگ یک باشد، مسیر با عدد تنوّع کمینه را بین دو رأس داده‌شده‌ی ‎$u$‎ و ‎$v$‎ پیدا کند.
  * ب) الگوریتمی چندجمله‌ای ارائه کنید که مسیری با عدد تنوّع حداکثر $t \times \sqrt{n}+\sqrt{n}$‎ بین دو رأس داده‌شده‌ی ‎$u$‎ و ‎$v$‎ پیدا کند. در این رابطه، ‎$t$‎ عدد تنوّع مسیر با کمترین عدد تنوّع بین ‎$u$‎ و ‎$v$‎ است.

  * [[سوال ۹|سوال بعد]]
  * [[سوال ۷|سوال قبل]]