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

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

• سوال بعد
• سوال قبل