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

توضیحات محصول

دانلود پاورپوینت Minimum Spanning Tree(MST Agorithm) با فرمت ppt ودر 37 اسلاید قابل ویرایش

قسمتی از متن پاورپوینت Minimum Spanning Tree(MST Agorithm)

فهرست مطالب

درخت پوشا

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

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

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

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

درخت پوشا

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

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

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

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

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

تعريف2: درخت پوشا با كمترين هزينه ،درخت پوشايي است كه كمترين هزينه را دارد.

3 الگوريتم براي بدست آوردن MSTوجود دارد.

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

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

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

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

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

1.تنها بايد از يال هاي گراف استفاده كند.

2.تنها بايد دقيقا از n-1يال استفاده كند.

3.از يال هايي كه دور ايجاد مي كنند نمي توانداستفاده كند.

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

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

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

يك يال بهTاضافه مي شود مشروط بر اينكه با يال هاي اضافه شده قبلي دور تشكيل ندهد.

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

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

E مجموعه اي از يال هاي گراف Gاست.عملياتي كه ميخواهيم انجام بدهيم:

1.تعيين يك يال با كمترين هزينه (ine 3)

2.حذف اين يال(ine 4)

1.T= Ø;

2.Whie ((T contains ess than n-1 edges) &&(E not empty)){

3. Choose an edge (v ,w) from E of owest cost;

4. Deete (v ,w) from E;

5. If ((v ,w) does not create a cyce in T) add (v ,w) to T;

6. Ese discard (v ,w);

7.}

8.If (T contains fewer than n-1 edges) cout

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

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

اثبات:

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

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

اثبات…

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

الگوريتم پريم مانند الگوريتم كراسكالMSTرا تشكيل ميدهد.

در تمام مراحل الگوريتم پريم،مجموعه يال هاي انتخاب شده درخت تشكيل ميدهد

…و لي در كراسكال در هر مرحله جنگل توليد مي شود.