====== سوال ۲ ======

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

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

  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]