۰
subtitle
ارسال: #۱
تست الگوریتم _ مهندسی کامپیوتر _ سال ۸۵ (گراف)
T درخت فراگیر کمینه برای یک گراف [tex]G=(V,E)[/tex] است .وزن یک یال از گراف را کاهش میدهیم.با چه مرتبه ای میتوان درخت فراگیر کمینه جدید را بدست آورد؟
جواب شده [tex]O(V)[/tex]
این مقدار ازکجا آمده؟ به نظر بنده این سوال بسیار مبهم است.زیرا اصلا معلوم نیست که یالی که کاهش وزن پیدا کرده به اندازه ای وزنش کم شده که در درخت پوشا هم قرار بگیرد یا خیر؟
جواب شده [tex]O(V)[/tex]
این مقدار ازکجا آمده؟ به نظر بنده این سوال بسیار مبهم است.زیرا اصلا معلوم نیست که یالی که کاهش وزن پیدا کرده به اندازه ای وزنش کم شده که در درخت پوشا هم قرار بگیرد یا خیر؟
۰
ارسال: #۲
سوال مهندسی کامپیوتر ۸۵:
اول اینکه میدونیم تعداد یال های درخت مینیمم پوشا برابر (تعداد راس‌ها -۱)=(v-1) حالا بررسی می کنیم ببینیم که یالی که وزنش کاهش پیدا کرده در درخت پوشایی که داریم هست یا نه که به اندازه تعداد یالها میشه زمان جست جو واگه در درخت نبود اون رو به درخت اضافه می کنیم و دوباره در همین درخت پوشای مینیمم جست و جو میکنیم و بزرگترین یال را حذف می کنیم در هر دو صورت درخت پوشای کمینه جدید با زمان برای مرحله اول---> v-1و برای مرحله دوم v (چون یک یال اضافه کردیم) پس در کل میشه (O(V
۰
ارسال: #۳
سوال مهندسی کامپیوتر ۸۵:
اگر یال جزو درخت بود که هیچ (یعنی کاهش بدیم یا ندیم بازم یال جزو درخت میمونه )
اما اگه یال عضو درخت نبود اون رو به درخت پوشای کمینه قبلی اضافه میکنیم ایجاد یک سیکل میکنه حالا یالی که در این سیکل بیشترین وزن رو داره حذف میکنیم.
اما اگه یال عضو درخت نبود اون رو به درخت پوشای کمینه قبلی اضافه میکنیم ایجاد یک سیکل میکنه حالا یالی که در این سیکل بیشترین وزن رو داره حذف میکنیم.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close