گراف زیگ‌زاگی گرافی‌ است که از تعدادی طبقه تشکیل شده است. در هر طبقه تعدادی راس قرار دارد و هر راس یک مقدار $x$ دارد. بین دو راس $a$ و $b$ در دو طبقه متوالی یال دوطرفه وجود دارد، اگر $x$ راس $a$ کمتر از $x$ راس $b$ باشد و راس $a$ در طبقه‌ی دقیقا یکی پایین‌تر از طبقه راس $b$ قرار داشته‌باشد.

1. الگوریتمی از $O(n)$ برای پیدا کردن طولانی‌ترین مسیر در یک گراف زیگ‌زاگی دو طبقه $n$ راسی ارائه دهید.
2. الگوریتمی از $O(n)$ برای پیدا کردن طولانی‌ترین مسیر در یک گراف زیگ‌زاگی سه طبقه $n$ راسی ارائه دهید.

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