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

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت Minimum Spanning Tree (MST Algorithm) قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

درخت  پوشا

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 Î TV and v Î 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الگوریتم وقتی تمام میشود که تنها یکه درخت تولید شده باشد.