پاورپوینت Minimum Spanning Tree (pptx) 23 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 23 اسلاید
قسمتی از متن PowerPoint (.pptx) :
Minimum Spanning Tree (MST Algorithm)
فهرست مطالب
درخت پوشا
درخت پوشای مینیمم
الگوریتم کراسکال
الگوریتم پرایم
الگوریتم سالین
درخت پوشا
درختT درخت پوشای گراف Gاست اگرT زیرگرافG باشد که حاوی تمامی رئوس G است.
درخت پوشا را می توان با استفاده از BFSو DFS بدست آورد…
یکی از خواص جالب درخت پوشا: درخت پوشا کوچک ترین زیرگراف است...
مثالی از درخت پوشا:
1
4
3
6
5
2
2
3
2
4
2
5
3
1
3
درخت پوشا)وزن=14)
درخت پوشا)وزن=11)
درخت پوشا)وزن=13)
درخت پوشای مینیمم
تعريف1:منظورازهزینه درخت پوشاي يك گراف بدون جهت وزن دار،مجموع هزينه (وزن)هاي يال هاي درخت پوشا است.
تعريف2: درخت پوشا با كمترين هزينه ،درخت پوشايي است كه كمترين هزينه را دارد.
3 الگوريتم براي بدست آوردن MSTوجود دارد.
الگوریتم کراسکال
الگوریتم پریم
الگوریتم سالین
براي ايجاد درخت پوشا با كمترين هزينه از معیار كمترين هزينه استفاده مي كنيم:
راه حل مطلوب تحت شرايط زير حاصل مي شود:
1.تنها بايد از يال هاي گراف استفاده كند.
2.تنها بايد دقيقا از n-1يال استفاده كند.
3.از يال هايي كه دور ايجاد مي كنند نمي توانداستفاده كند.
درخت پوشای مینیمم- ادامه
الگوریتم کراسکال
اين الگوريتم با اضافه كردن يال ها به صورت مرحله به مرحله بهT،درخت پوشا با كمترين هزينه ي T را توليد مي كند.
يال ها به ترتيب غير نزولي انتخاب مي شوند.
يك يال بهTاضافه مي شود مشروط بر اينكه با يال هاي اضافه شده قبلي دور تشكيل ندهد.
گرافGهمبند است وn>0راس دارد پس دقيقا n-1 يال براي اضافه شدن در Tانتخاب ميشود.
0
5
4
1
6
2
3
10
28
16
12
18
22
25
24
14
(G)
4
1
6
2
3
0
5
4
1
6
2
3
10
12
14
16
22
25
(MST)
مثال - الگوریتم کراسکال
E مجموعه اي از يال هاي گراف Gاست.عملياتي كه ميخواهيم انجام بدهيم:
1.تعيين يك يال با كمترين هزينه (line 3)
2.حذف اين يال(line 4)
1.T= Ø;
2.While ((T contains less than n-1 edges) &&(E not empty)){
3. Choose an edge (v ,w) from E of lowest cost;
4. Delete (v ,w) from E;
5. If ((v ,w) does not create a cycle in T) add (v ,w) to T;
6. Else discard (v ,w);
7.}
8.If (T contains fewer than n-1 edges) cout<<“no spanning tree”<
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
قیمت: 42٬000 تومان
