جستجوی درخت فراگیر قوی با مقادیر بازه ای توسط تجزیه بندر

برقراری ارتباط از راه دور، انسان را به بررسی درخت فراگیر کمینه، با مقادیر بازهای سوق داد و از آنجا که حل مساله درخت فراگیر کمینه به درک قیمت واقعی یال های گراف وابسته است، مساله درخت فراگیر قوی تعریف شده است. مساله درخت فراگیر قوی، به عنوان رده ای از مساله درخت فراگیر کمینه به حساب می آید که در آن یال ها به جای داشتن مقادیر ثابت، مقادیر بازه ای به خود می گیرند. در این مقاله برای یافتن درخت فراگیر قوی روشی تجزیه بندر استفاده می کنیم، در مسایل عملی، بسیاری از مسایل برنامه ریزی خطی از لحاظ ابعادی آنقدر بزرگ می باشند. که حتی در رایانه های پیشرفته امروزی آنها را نمی توان حل نمود. در این چنین مسایلی، باید از روش هایی استفاده کرد. که مسایل بزرگ را به تعدادی مسایلی کوچک قابل حل تبدیل کند و سپس از طریق حل این مسایل کوچک به حل مساله بزرگ اولیه رسید.

Keywords:

درخت قوی , تجزیه بندر , گراف , دوگان , نقاط فرین