مخفف STP
Steiner Tree Problem
31
مسئله درخت اشتاینر با مسئله درخت پوشای مینیمم مشابهت دارد: فرض کنید مجموعه رئوس V داده شدهاند، می خواهیم آنها را با یک گراف با کمترین وزن به هم متصل میکنیم.به طوری که حاصل جمع وزنهای همه یالها کمینه شود.تفاوت بین مسئله درخت اشتاینر و مسئله درخت پوشای مینیمم این است که در مسئله درخت اشتاینر، رئوس میانه و یال ممکن است به گراف اضافه شوند تا وزن درخت پوشا را کاهش دهند.این رئوس جدید برای کاهش وزن کلی اتصالات معرفی میشوند و نقاط اشتاینر یا رئوس اشتاینر نام دارند.ثابت شدهاست که اتصالات به دست آمده یک درخت را تشکیل میدهند، که درخت اشتاینر نام دارد.ممکن است برای مجموعهای از رئوس درختهای اشتاینر زیادی وجود داشته باشند. مسئله درخت اشتاینر در طراحی فیزیکی مدارات VLSI یا شبکه کا ربرد فراوانی دارد. خیلی از نسخههای مسئله اشتاینر NP-complete هستند. ارسال نظر