پاورپوینت الگوريتم های كراسكل و پريم و سولين

دانلود پاورپوینت با موضوع الگوريتم های كراسكل و پريم و سولين،

در قالب ppt و در 11 اسلاید، قابل ویرایش.

اجزاي دو اتصالي و نقاط اتصال
3-6 درختان پوشاي با حداقل هزينه
3-6 درختان پوشاي با حداقل هزينه
3-6 الگوريتم كراسكل
در
اين روش ، درخت پوشاي با کمترين هزينه T ، لبه به لبه ساخته مي شود. لبه
هاي مورد استفاده در T ، به ترتيب صعودي وزن ها مي باشد. يک لبه در T خواهد
بود، اگر با لبه هاي قبل که در T بوده اند ، تشکيل يک حلقه ندهد چون G
متصل است و داراي n > 0 راس است ، دقيقا n – 1 لبه براي T انتخاب مي
شود.
اين الگوريتم با نام راشال نيز شناخته شده است
3-6 الگوريتم كراسكل(مثال)
3-6 الگوريتم كراسكل(راشال)
3-6 الگوريتم پريم
 الگوريتم پريم مانند الگوريتم كراسكل، در هر زمان يک لبه از درخت پوشاي حداقل هزينه را مي سازد.
هر
چند در هر مرحله الگوريتم پريم، مجموعه لبه ها انتخاب شده يک درخت را
تشکيل مي دهند . در مقابل ، مجموعه لبه هاي انتخاب شده در الگوريتم كراسكل
در هر مرحله يک جنگل را تشکيل مي دهند.
 الگوريتم پريم با يک درخت مانند T ، که تنها شامل يک راس است، شروع مي کند. اين مي تواند هر يک از رئوس در گراف اصلي باشد.
سپس
يک لبه با کمترين هزينه مانند  به T اضافه مي شود به نحوي که    
                    از خود يک درخت مي باشد. اين عمل را تا زماني که T
شامل n – 1 لبه باشد ، ادامه مي دهيم.