فرمت فایل :power point( قابل ویرایش) تعداد اسلاید: 10 اسلاید
هزینه یک درخت پوشای یک گراف دارای وزن ، مجموع هزینه های (وزن های) لبه ها در درخت پوشا می باشد.
درخت پوشای حداقل هزینه ، درخت پوشایی است که دارای کمترین هزینه باشد.
برای به دست آوردن درخت پوشای حداقل هزینه یک گراف وزن دارمتصل می توان از سه الگوریتم متفاوت استفاده نمود :
الگوریتم کراسکل، الگوریتم پریم ، الگوریتم سولین
هر سه روش از یک طراحی الگوریتمی به نام خط مشی greedy استفاده می کنند.
برای درخت های پوشا از ملاک کمترین هزینه استفاده می شود. روش ما باید دارای شرایط زیر باشد :
باید فقط از لبه های داخل گراف استفاده کنیم.
باید دقیقا از n-1 لبه استفاده کنیم.
نباید از لبه هایی که ایجاد یک حلقه می کنند ، استفاده کنیم.
پاورپوینت درباره الگوریتم کراسکال و پریم
