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


گراف ساده‌ی وزن‌دار ‎$G$‎ را با وزن‌های نامنفی در نظر بگیرید. فرض کنید مجموعه‌ رئوس ‎$G$‎ از دو مجموعه‌ رأس جدا از هم و ناتهی ‎$R‎, ‎S$‎ تشکیل شده باشد. می‌خواهیم یک زیردرخت با وزن کمینه از ‎$G$‎ انتخاب کنیم؛ طوری که به ازای هر رأس از ‎$R$‎، دست کم یک یال در درخت وجود داشته باشد که به آن رأس وصل باشد. به این زیردرخت با وزن کمینه، درخت اشتاینر می‌گوییم.

  - مسئله‌ای دیگر را در نظر بگیرید. گراف ساده‌ی وزن‌دار ‎$H$‎ با وزن‌های مثبت داده شده است. فرض کنید مجموعه رئوس ‎$H$‎ از ‎۲‎ مجموعه رأس جدا از هم و ناتهی ‎$P‎, ‎Q$‎ تشکیل شده باشد. می‌خواهیم یک زیرگراف با وزن کمینه از ‎$H$‎ انتخاب کنیم؛ طوری که به ازای هر رأس مانند ‎$u$‎ از ‎$P$‎، رأسی مانند ‎$v$‎ از ‎$Q$‎ وجود داشته باشد که ‎$u$‎ به ‎$v$‎ مسیر داشته باشد. ثابت کنید برای یافتن این زیرگراف با وزن کمینه، الگوریتم با زمان چندجمله‌ای وجود دارد.
  - مسئله‌ای دیگر را در نظر بگیرید. گراف ساده‌ی وزن‌دار ‎$H$‎ با وزن‌های مثبت داده شده است. فرض کنید مجموعه رئوس ‎$H$‎ از ‎۳‎ مجموعه رأس جدا از هم و ناتهی ‎$P‎, ‎Q‎, ‎T$‎ تشکیل شده باشد. می‌خواهیم یک زیرگراف با وزن کمینه از ‎$H$‎ انتخاب کنیم؛ طوری که به ازای هر رأس مانند ‎$u$‎ از ‎$P$‎، رأسی مانند ‎$v$‎ از ‎$Q$‎ وجود داشته باشد که ‎$u$‎ به ‎$v$‎ مسیر داشته باشد. ثابت کنید یافتن این زیرگراف با وزن کمینه، الگوریتم با زمان چندجمله‌ای دارد اگر و تنها اگر یافتن درخت اشتاینر الگوریتم با زمان چندجمله‌ای داشته باشد. ‎

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