تفاوت میان نسخه‌های «درخت پوشای کمینه»

جز
اصلاح فاصله مجازی + اصلاح نویسه با ویرایشگر خودکار فارسی
جز (replaced: ها ← ‌ها (2)، های ← ‌های ، ه ی ← هٔ ، می شود ← می‌شود، داشته است ← داشته‌است، می توان ← می‌توان ، می با ویرایشگر خودکار فارسی)
جز (اصلاح فاصله مجازی + اصلاح نویسه با ویرایشگر خودکار فارسی)
'''درخت پوشای کمینه''' یا درخت فراگیر مینیمم در [[گراف|گراف‌های]] ارزش دار (وزن دار) ساخته می‌شود.
 
فرض کنید گراف یک [[گراف همبند]] باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک [[درخت پوشا]] از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آنراآن را دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک [[گراف جهت دار]] متصل می‌توان از الگوریتم‌های متفاوتی استفاده نمود.سه [[الگوریتم]] معروف پیدا کردن درخت پوشای کمینه عبارتند از :
[[الگوریتم کروسکال]]،
[[الگوریتم پریم]]،
امکان وجود بیش از یک درخت پوشای کمینه وجود دارد، برای مثال اگر تمام یال‌ها وزن برابری داشته باشند، تمام زیر در خت‌ها درخت پوشای کمینه هستند. اگر وزن هر دو یال با هم متفاوت باشد، تنها یک درخت پوشای کمینه خواهیم داشت.
 
کم وزن ترینوزن‌ترین یال در برش گراف
 
ادعا: اگر گراف را به دو مجموعه V و V′ از راس‌ها افراز کنیم، کم‌وزن ترینکم‌وزن‌ترین یال بین یال‌هایی که یک طرفشان در مجموعه V و طرف دیگرشان در مجموعه V′ است باید جزء درخت پوشای کمینه باشد. (اگر چند یال با کم‌ترین وزن وجود داشت، باید دقیقا یکی از آنهاآن‌ها جزء درخت پوشای کمینه باشد).
 
کم‌وزن ترینکم‌وزن‌ترین یال گراف
 
اگر کم‌وزن ترینکم‌وزن‌ترین یال گراف یکتا باشد در هر درخت پوشای کمینه‌ای وجود خواهد داشت.
 
پروزن ترینپروزن‌ترین یال هر دور
 
اگر یالی در یک دور از تمام یال‌های موجود در آن دور وزنش بیشتر باشد، نمی‌تواند در درخت پوشای کمینه قرار بگیرد. فرض خلف: فرض کنید این یال در یک درخت پوشای کمینه وجود دارد، اگر آنراآن را حذف کنیم درخت به دو مولف تقسیم می‌شود و دور مذکور در گراف اصلی بدون این یال یک مسیر بین این دو مؤلفه می‌شود. یالی از این مسیر که این مسیر را از این مؤلفه به آن مؤلفه منتقل می‌کند جایگزین یال حذف شده به درخت اضافه کنید(ممکن است چند یال این کار را بکنند که مهم نیست کدام را انتخاب می‌کنیم). این یال کم‌وزن تر است پس مجموع وزن‌های یال‌های درخت جدید کم تر است که با کمینه بودن درخت اول در تناقض است.
 
==کاربرد درخت پوشای کمینه==
در مسائلی که هدف ایجاد شبکه‌ای است که برای ایجاد ارتباط بین هر دو عضو آن هزینه‌ای باید بپردازیم و می‌خواهیم در نهایت در این شبکه بین هر دو عضو ارتباط وجود داشته باشد، درخت پوشای کمینه همان کم هزینه‌ترین شبکه است. برای مثال فرض کنید در کشوری می‌خواهیم طوری جاده‌سازی کنیم که بتوان از هر شهری به هر شهر دیگری سفر کرد و هزینه ساخت جاده بین هر دو شهر را داریم(این هزینه می‌تواند تابعی بر اساس فاصله ۲ شهر، آب و هوای بین دو شهر فاصله آنهاآن‌ها از شرکت راه‌سازی و … باشد). برای پیدا کردن کم هزینه ترینهزینه‌ترین راه، باید درخت پوشای کمینه را بیابیم.
 
== الگوریتم کروسکال ==
در الگوریتم کراسکال یال‌های گراف را به ترتیب صعودی مرتب می کنیم. از اولین (کوچکترین) یال شروع کرده و هر یال را به گراف اضافه می کنیم به شرط اینکه دور در گراف ایجاد نگردد. این روال را آنقدر ادامه می دهیم تا درخت پوشای بهینه تشکیل گردد.
 
این الگوریتم نیزمشابه الگوریتم پریم برای یافتن درخت پوشای کمینهٔ یک گراف به کارمی رود.دراین الگوریتم ابتدایال هاازکمترین وزن به بیشترین وزن مرتب می گردندسپس یال هابه ترتیب انتخاب شده واگریالی ایجادحلقه کندوکنارگذاشته می‌شود.عملیات هنگامی خاتمه می یابدکه تمام رأس هابه هم وصل شوند یااینکه تعداد یال‌های موجود در F برابر n-1 شود که n تعداد رأس‌ها است. که در بعضی کتابهاکتاب‌ها با نام راشال مطرح شده‌است. شکل زیر مراحل کار را برای یک گراف فرضی نشان می‌دهد.
 
بیشتر زمان درالگوریتم کروسکال مربوط به مرتب سازی یالهاست، پس اگر تعداد یال e باشد زمان این الگوریتم از مرتبه (e lg e) Ѳ خواهد بود.
۱۳۳٬۲۴۲

ویرایش