Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:الگوریتم ها:سوال ۹

سوال ۹

گراف G که رئوس آن با k رنگ، رنگ‌آمیزی شده‌اند به ما داده شده است (دقت کنید که ممکن است رنگ‌آمیزی خوب نباشد، یعنی دو راس مجاور رنگ یکسانی داشته باشند). حال دو راس s و t را به ما می‌دهند و از ما می‌خواهند که مسیری از s به t که از هر رنگ دقیقا یکی داشته باشد را در زمان در خروجی بدهیم (دقت کنید که ممکن است چنین مسیری وجود نداشته باشد و در خروجی Impossible را بدهیم). الگوریتمی در زمان O(2k×f(n)) که در آن f(n) یک چند جمله‌ای بر حسب n می‌باشد، برای این کار ارائه دهید.


ابزار صفحه