درخت steiner

تعریف مساله ی درخت steiner: یک گراف وزن دار و زیرمجموعه ای از راسهای آن T داده شده است. درخت با کمترین هزینه را پیدا کنید که همه ی راسهای T را به هم وصل می کند. ("راسهای کمکی" راسهایی هستند که در گراف هستند اما در T نیستند.)

مساله: یک گراف وزن دار و زیر مجموعه ای از راسهای آن داده شده R، می خواهیم حداقل هزینه ی اتصال زیرگراف پوشای R را به دست بیاوریم. راسهای R را پایانی و بقیه راسهای گراف را استینر می نامیم.

نکته 1: زیرگراف پوشای R یک درخت است. (اگر نباشد می توانیم از آن یال حذف کنیم و هزینه کم شود اما همبندی حفظ می شود.)

نکته 2: می توانیم از راسهای غیرپایانی (استینر) برای به دست آوردن درخت استینر استفاده کنیم.

ادعا 1: بدون از دست رفتن عمومیت می توانیم فرض کنیم گراف اولیه ما (G) گراف کامل است.

Gc: تکمیل فاصله ای گراف G: هزینه ی یال u به v را به ازای هر زوج راس گراف طول کوتاهترین مسیر بین آنها در G قرار می دهیم. هزینه ی یالهای Gc یک فاصله است. (4 خاصیت فاصله را دارد.)

لم 1: اگر T درخت پوشای R در Gc باشد، می تواینم زیردرختی در G پیدا کنیم T' که R را بپوشاند و هزینه ی آن کمتر از هزینه ی T در Gc باشد.

هر یال T' یک مسیر در G است پس اجتماع یالهای این مسیرها یک گراف می شود که هزینه ی آن همان هزینه ی T' است. پس روی آن می توانیم یک درخت مثل T بسازیم و هزینه ی آن کمتر خواهد بود.

برای حل از به دست آوردن کران پایین شروع می کنیم. ایده ی دور فروشنده ی دوره گرد را برای به دست آوردن کران پایین برای درخت استینر بهینه استفاده می کنیم.

لم: فرش کنید Gc(R) زیرگراف القایی توسط R از Gc باشد. هزینه ی MST روی Gc(R) حداکثر به اندازه ی هزینه ی دور فروشنده ی دوره گرد بهینه روی Gc(R) است.

(اثبات: به پست فروشنده دوره گرد مراجعه کنید!)

لم: هزینه ی دور فروشنده ی دوره گرد (TSP) بهینه روی Gc(R) حداکثر دو برابر OPT (درخت استینر متناظر R روی گراف Gc(R) ) است.

اثبات: 

(ادامه دارد..! در ضمن اسم درست این درخت اشتاینر بود نه استینر! )