T درخت فراگیر کمینه برای یک گراف [tex]G=(V,E)[/tex] است .وزن یک یال از گراف را کاهش میدهیم.با چه مرتبه ای میتوان درخت فراگیر کمینه جدید را بدست آورد؟
جواب شده [tex]O(V)[/tex]
این مقدار ازکجا آمده؟ به نظر بنده این سوال بسیار مبهم است.زیرا اصلا معلوم نیست که یالی که کاهش وزن پیدا کرده به اندازه ای وزنش کم شده که در درخت پوشا هم قرار بگیرد یا خیر؟
اول اینکه میدونیم تعداد یال های درخت مینیمم پوشا برابر (تعداد راسها -۱)=(v-1) حالا بررسی می کنیم ببینیم که یالی که وزنش کاهش پیدا کرده در درخت پوشایی که داریم هست یا نه که به اندازه تعداد یالها میشه زمان جست جو واگه در درخت نبود اون رو به درخت اضافه می کنیم و دوباره در همین درخت پوشای مینیمم جست و جو میکنیم و بزرگترین یال را حذف می کنیم در هر دو صورت درخت پوشای کمینه جدید با زمان برای مرحله اول---> v-1و برای مرحله دوم v (چون یک یال اضافه کردیم) پس در کل میشه (O(V
اگر یال جزو درخت بود که هیچ (یعنی کاهش بدیم یا ندیم بازم یال جزو درخت میمونه )
اما اگه یال عضو درخت نبود اون رو به درخت پوشای کمینه قبلی اضافه میکنیم ایجاد یک سیکل میکنه حالا یالی که در این سیکل بیشترین وزن رو داره حذف میکنیم.