توضیحات
مسئله درخت اشتاینر، که به افتخار یاکوب اشتاینر مبدع آن نام گذاری شده، کوچکترین درخت وزن داری است که شامل تعدادی از گره‌های خاص به نام ترمینال باشد.
در این مسئله یک گراف وزن دارG=(E,V) و یک زیرمجموعه از رئوس گراف T که مجموعه ترمینال‌ها نام دارد ارائه می‌گردد. و هدف پیدا کردن GT=(V’,E’) با کمترین هزینه‌است که E’⊆E و T⊆V’⊆V
مسئله درخت اشتاینر با مسئله درخت پوشای مینیمم مشابهت دارد: فرض کنید مجموعه رئوس V داده شده‌اند، می خواهیم آنها را با یک گراف با کمترین وزن به هم متصل کنیم. به طوری که حاصل جمع وزنهای همه یالها کمینه شود. تفاوت بین مسئله درخت اشتاینر و مسئله درخت پوشای مینیمم این است که در مسئله درخت اشتاینر، رئوس میانه و یال ممکن است به گراف اضافه شوند تا وزن درخت پوشا را کاهش دهند. این رئوس جدید برای کاهش وزن کلی اتصالات معرفی می‌شوند و نقاط اشتاینر یا رئوس اشتاینر نام دارند. ثابت شده‌است که اتصالات به دست آمده یک درخت را تشکیل می‌دهند، که درخت اشتاینر نام دارد. ممکن است برای مجموعه‌ای از رئوس درختهای اشتاینر زیادی وجود داشته باشند.
درخت اشتاینر متریک مسئله ای است که باید پیاده سازی شود:
درختان اشتاینر در چهار چوب گراف وزندار مورد مطالعه قرار می‌گیرند. و آن را به صورت G=(E,V,W) نشان می‌دهیم. حال دو نوع مشکل وجود دارد: در مسئله بهینه سازی مربوط به درخت اشتاینر، هدف پیدا کردن کم وزن‌ترین درخت اشتاینر است، در مسئله تصمیم گیری، ما مقدار k را در نظر میگیریم و هدف تعیین این است که آیا درخت اشتاینری از وزن کل حداکثر k وجود دارد. ما می‌توانیم توجه خود را به مورد خاصی کهG گراف کامل باشد، محدود کنیم. هر راسی در فضای متریک محدود به یک نقطه‌است و W(e) برای هر یال
e∈E متناظر با فاصله در فضا است. وزن یالها در نامساوی مثلث صدق می‌کند. این نوع به عنوان مسئله درخت اشتاینر متریک شناخته شده‌است. می‌توان مثالی غیر متریک از مسئله درخت اشتاینر را در زمان از درجه پیچیدگی چندجمله‌ای به عنوان مثال معادل مسئله درخت اشتاینر متریک تبدیل کرد؛ این تغییر ضریب تقریب را حفظ می‌کند
خروجی
دیدگاهها
هیچ دیدگاهی برای این محصول نوشته نشده است.