یال‌های یک گراف با تعدادی رنگ، رنگ‌آمیزی شده‌اند. «عدد تنوّع» برای یک مسیر، تعداد رنگ‌های موجود در یال‌های آن مسیر است. تعداد بخش‌های یک رنگ مانند $c$ به این صورت به دست می‌آید که صرفاً یال‌های به رنگ $c$ را در گراف درنظرمی‌گیریم و تعداد مؤلفه‌هایی از این گراف حاصل را که حداقل یک یال دارند، تعداد بخش‌های این رنگ می‌نامیم. برای حل قسمت ب می‌توانید قسمت الف را درست فرض کنید.

• الف) الگوریتمی چندجمله‌ای ارائه کنید که اگر در گراف ما تعداد بخش‌های هر رنگ یک باشد، مسیر با عدد تنوّع کمینه را بین دو رأس داده‌شده‌ی $u$ و $v$ پیدا کند.
• ب) الگوریتمی چندجمله‌ای ارائه کنید که مسیری با عدد تنوّع حداکثر $t \times \sqrt{n}+\sqrt{n}$ بین دو رأس داده‌شده‌ی $u$ و $v$ پیدا کند. در این رابطه، $t$ عدد تنوّع مسیر با کمترین عدد تنوّع بین $u$ و $v$ است.