پاورپوینت Minimum Spanning Tree(MST Algorithm)

توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد

  پاورپوینت Minimum Spanning Tree(MST Algorithm) دارای ۲۳ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است

فایل پاور پوینت پاورپوینت Minimum Spanning Tree(MST Algorithm)  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

---

لطفا به نکات زیر در هنگام خرید

دانلود پاورپوینت Minimum Spanning Tree(MST Algorithm)

توجه فرمایید.

۱-در این مطلب، متن اسلاید های اولیه 

دانلود پاورپوینت Minimum Spanning Tree(MST Algorithm)

قرار داده شده است

۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد

۴-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است

---

بخشی از متن پاورپوینت Minimum Spanning Tree(MST Algorithm) :

اسلاید ۱ :

درخت  پوشا

lدرختT درخت  پوشای گراف Gاست اگرT زیرگرافG  باشد که حاوی تمامی رئوس G است.

lدرخت  پوشا را می توان با استفاده از BFSو DFS بدست آورد…

lیکی از خواص جالب درخت  پوشا: درخت  پوشا کوچک ترین زیرگراف است;

اسلاید ۲ :

درخت  پوشای مینیمم

lتعریف۱:منظورازهزینه درخت پوشای یک گراف بدون جهت وزن دار،مجموع هزینه (وزن)های یال های درخت پوشا است.

lتعریف۲: درخت پوشا با کمترین هزینه ،درخت پوشایی است که کمترین هزینه را دارد.

l3 الگوریتم برای بدست آوردن MSTوجود دارد.

–الگوریتم کراسکال    

–الگوریتم پریم    

–الگوریتم سالین    

l

اسلاید ۳ :

درخت  پوشای مینیمم- ادامه

lبرای ایجاد درخت پوشا با کمترین هزینه از معیار کمترین هزینه استفاده می کنیم:

lراه حل مطلوب تحت شرایط زیر حاصل می شود:

l

۱تنها باید از یال های گراف استفاده کند.

۲تنها باید دقیقا از n-1یال استفاده کند.

۳از یال هایی که دور ایجاد می کنند نمی توانداستفاده کند.

اسلاید ۴ :

الگوریتم کراسکال

lاین الگوریتم با اضافه کردن یال ها به صورت مرحله به مرحله بهT،درخت پوشا با کمترین هزینه ی T را تولید می کند.

lیال ها به ترتیب غیر نزولی انتخاب می شوند.

lیک یال بهTاضافه می شود مشروط بر اینکه با یال های اضافه شده قبلی دور تشکیل ندهد.

lگرافGهمبند است وn>0راس دارد پس دقیقا n-1 یال برای اضافه شدن در Tانتخاب میشود.

اسلاید ۵ :

الگوریتم کراسکال

lE مجموعه ای از یال های گراف Gاست.عملیاتی که میخواهیم انجام بدهیم:

l1.تعیین یک یال با کمترین هزینه (line 3)

l2.حذف این یال(line 4)

اسلاید ۶ :

قضیه الگوریتم کراسکال

lاگر Gیک گراف همبند بدون جهت باشد آنگاه الگوریتم کراسکال، یک درخت پوشا با کمترین هزینه تولید می کند.

lاثبات:

–الف- در صورت وجود یک درخت پوشا،روش کراسکال یک درخت پوشا تولید می کند.

–ب- درخت پوشای تولید شده کمترین هزینه را دارد.

lاثبات;

اسلاید ۷ :

الگوریتم پریم

lالگوریتم پریم مانند الگوریتم کراسکالMSTرا تشکیل میدهد.

lدر تمام مراحل الگوریتم پریم،مجموعه یال های انتخاب شده درخت تشکیل میدهد

l;و لی در کراسکال در هر مرحله جنگل تولید می شود.

اسلاید ۸ :

الگوریتم پریم – پیاده سازی

lبرای هر راس داریم:

–kv :آیا v دیده شده است

–dv :کمترین  وزن برای راس  v کدام است

–pv :کدام راس ابتدا قرار می گیرد؟

اسلاید ۹ :

الگوریتم پریم – پیاده سازی

//Assume that G has at least one vertex.

TV={0};//start with vertex 0 and no edges

For (T=null; contains fewer than n-1 edges; add (u, v) to T)

{

   let (u, v) be a least-cost edge such that u I TV and v I TV;

      If (there is no such edge) break;

   Add v to TV;

}

If (T contains fewer than n-1 edges) cout <<“no spanning tree”<< endl;

اسلاید ۱۰ :

الگوریتم سالین

lالگوریتم سالین در هر مرحله چند یال مختلف را انتخاب میکند.

lدر آغاز هر مرحله ،یال های انتخاب شده با تمامn راس،یک جنگل پوشا راتشکیل میدهد.

lدر شروع مرحله اول،مجموعه یالهای انتخاب شده تهی است.

lالگوریتم وقتی تمام میشود که تنها یکه درخت تولید شده باشد.