با عرض سلام
دوستان بی زحمت سوال زیر رو یه راهنمایی می فرمایید؟
با تشکر
(۲۲ فروردین ۱۳۹۶ ۱۱:۴۷ ب.ظ)alimamala نوشته شده توسط: با عرض سلام
دوستان بی زحمت سوال زیر رو یه راهنمایی می فرمایید؟
با تشکر
اول در درخت T یک جستجو انجام میدیم که ببینیم یال E در اون وجود داره یا نه ، چون اگه یال E در درخت T قرار داشته باشه بعد از کاهش وزن یال این عمل در درخت هم اثر میکنه پس کار تموم میشه یعنی وزن یال E در درخت هم کاهش پیدا میکنه یافتن همچین یالی در درخت باتوجه به اینکه تعداد رئوس از تعداد یال بیشتر هستش ( درخت هست و سیکل نداریم ) میشه از [tex]O(|V|)[/tex] در صورتی که یال مورد نظر در درخت T نباشد پس باید جستجو در گراف G صورت بگیره سپس بعد از یافتن یال E از گراف G ، این یال به درخت T اضافه بشه که باز از مرتبه [tex]O(|V|)[/tex] میشه یعنی رئوس رو ببین یال و پیدا کن ، حالا بعد از اضافه کردن یال به درخت طبیعتا" دیگه از تعریف درخت خارج میشیم چون تعداد یال و رئوس یکسان شد یعنی یک سیکل بوجود میاد کافیه یک یال حذف کنیم پس در کل میشه از مرتبه [tex]O(|V|)[/tex]
مرسی دوست عزیز
موفق و سربلند باشید