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

۳٬۳۲۶ بایت اضافه‌شده ،  ۴ سال پیش
جز
بدون خلاصه ویرایش
برچسب: نیازمند بازبینی
جز
برچسب: نیازمند بازبینی
 
فرض کنید گراف یک [[گراف همبند]] باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک [[درخت پوشا]] از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یال‌های آنرا دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درخت‌های پوشای آن گراف، مجموع وزن یال‌های آن، کمترین مقدار ممکن باشد.برای به دست آوردن درخت پوشای بهینه یک [[گراف جهت دار]] متصل می توان از الگوریتم‌های متفاوتی استفاده نمود.سه [[الگوریتم]] معروف پیدا کردن درخت پوشای کمینه عبارتند از :
[[الگوریتم کروسکال]]،
[[الگوریتم پریم]]،
[[الگوریتم سولینبروکا]](سولین)،
[[الگوریتم حذف معکوس]]
 
==ویژگی های درخت پوشای کمینه==
تعداد حالات ممکن
 
امکان وجود بیش از یک درخت پوشای کمینه وجود دارد، برای مثال اگر تمام یال‌ها وزن برابری داشته باشند، تمام زیر در خت ها درخت پوشای کمینه هستند. اگر وزن هر دو یال با هم متفاوت باشد، تنها یک درخت پوشای کمینه خواهیم داشت.
 
کم وزن ترین یال در برش گراف
 
ادعا: اگر گراف را به دو مجموعه V و V′ از راس‌ها افراز کنیم، کم‌وزن ترین یال بین یال‌هایی که یک طرفشان در مجموعه V و طرف دیگرشان در مجموعه V′ است باید جزء درخت پوشای کمینه باشد. (اگر چند یال با کم‌ترین وزن وجود داشت، باید دقیقا یکی از آنها جزء درخت پوشای کمینه باشد).
 
کم‌وزن ترین یال گراف
 
اگر کم‌وزن ترین یال گراف یکتا باشد در هر درخت پوشای کمینه‌ای وجود خواهد داشت.
 
پروزن ترین یال هر دور
 
اگر یالی در یک دور از تمام یال‌های موجود در آن دور وزنش بیشتر باشد، نمی‌تواند در درخت پوشای کمینه قرار بگیرد. فرض خلف: فرض کنید این یال در یک درخت پوشای کمینه وجود دارد، اگر آنرا حذف کنیم درخت به دو مولف تقسیم می‌شود و دور مذکور در گراف اصلی بدون این یال یک مسیر بین این دو مولفه می‌شود. یالی از این مسیر که این مسیر را از این مولفه به آن مولفه منتقل می‌کند جایگزین یال حذف شده به درخت اضافه کنید(ممکن است چند یال این کار را بکنند که مهم نیست کدام را انتخاب می‌کنیم). این یال کم‌وزن تر است پس مجموع وزن‌های یال‌های درخت جدید کم تر است که با کمینه بودن درخت اول در تناقض است.
 
==کاربرد درخت پوشای کمینه==
در مسائلی که هدف ایجاد شبکه‌ای است که برای ایجاد ارتباط بین هر دو عضو آن هزینه‌ای باید بپردازیم و می‌خواهیم در نهایت در این شبکه بین هر دو عضو ارتباط وجود داشته باشد، درخت پوشای کمینه همان کم هزینه‌ترین شبکه است. برای مثال فرض کنید در کشوری می‌خواهیم طوری جاده‌سازی کینم که بتوان از هر شهری به هر شهر دیگری سفر کرد و هزینه ساخت جاده بین هر دو شهر را داریم(این هزینه می‌تواند تابعی بر اساس فاصله ۲ شهر، آب و هوای بین دو شهر فاصله آنها از شرکت راه‌سازی و … باشد). برای پیدا کردن کم هزینه ترین راه، باید درخت پوشای کمینه را بیابیم.
 
== الگوریتم کروسکال ==
{{پانویس}}
{{چپ‌چین}}
* [//mst.sheikhoo.ir درخت پوشای کمینه]
* [//en.wikipedia.org/wiki/Kruskal_algorithm]
* [//en.wikipedia.org/wiki/Prim_algorithmKruskal_algorithm Kruskal_algorithm ]
* [//en.wikipedia.org/wiki/Kruskal_algorithmPrim_algorithm Prim_algorithm ]
* [http://www.jozve-computer.blogfa.com]
* [http://www.erfanrad.blogfa.com]
{{پایان چپ‌چین}}
 
{{الگوریتم‌های بهینه‌سازی}}
[[رده:درخت پوشا]]
۱

ویرایش