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

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

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