دسته | علوم انسانی |
---|---|
حجم | 160/9 کیلوبایت |
صفحه | 37 |
فرمت | pptx |
قیمت | 24000 تومان |
دانلود پاورپوینت درخت پوشای مینیمم Minimum spanning tree در قالب 37 اسلاید و با فرمت pptx
درخت پوشای کمینه یا درخت فراگیر مینیمم در گرافهای ارزش دار (وزن دار) ساخته میشود.
فرض کنید گراف یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد) منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یالهای آن را دربر گیرد. منظور از درخت پوشای مینیمم (برای گراف همبند وزن دار) درختی است که بین درختهای پوشای آن گراف، مجموع وزن یالهای آن، کمترین مقدار ممکن باشد. برای به دست آوردن درخت پوشای بهینه یک گراف جهت دار متصل میتوان از الگوریتمهای متفاوتی استفاده نمود. چهار الگوریتم معروف پیدا کردن درخت پوشای کمینه عبارتند از: الگوریتم کروسکال، الگوریتم پریم، الگوریتم بروکا (سولین) و الگوریتم حذف معکوس.
فهرست مطالب :
درخت پوشا
درخت پوشای مینیمم
الگوریتم کراسکال
الگوریتم پرایم
الگوریتم سالین