مرجع کلمات و اصطلاحات اختصاری

مسئله درخت اشتاینر، که به افتخار یاکوب اشتاینر مبدع آن نام گذاری شده، کوچکترین درخت وزن داری است که شامل تعدادی از گره‌های خاص به نام ترمینال باشد. در این مسئله یک گراف وزن دار(G=(V,E و یک زیرمجموعه از رئوس گراف (T⊆V) که مجموعه ترمینال‌ها نام دارد ارائه می‌گردد و هدف پیدا کردن(`GT=(V`,E با کمترین هزینه‌است.که. E`⊆Eو T⊆V`⊆V مسئله درخت اشتاینر دارای کاربردهای فراوانی نظیر مسیر یابی یک به چند در شبکه‌های رایانه‌ای، سامانه‌های ترابری، پلیس امداد، ایستگاه‌های پستی و کاربردهای دیگر می‌باشد.

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

ارسال نظر