دانلود فایل پاورپوینت اجزای دو اتصالی و نقاط اتصال 10 اسلاید
— پاورپوینت شامل تصاویر میباشد —-
اسلاید ۱ :
۲-۶ اجزای دو اتصالی و نقاط اتصال
نقطه اتصال : یک راس مانند v از گراف G می باشد به نحوی که حذف راس v همراه با تمام لبه های متلاقی با v ، گرافی به نام ایجادمی کند که حداقل دارای دو جز متصل است.
گراف دو اتصالی یک گراف متصل است اگر فاقد نقاط اتصالی باشد .
اسلاید ۲ :
۳-۶ درختان پوشای با حداقل هزینه
هزینه یک درخت پوشای یک گراف دارای وزن ، مجموع هزینه های (وزن های) لبه ها در درخت پوشا می باشد.
درخت پوشای حداقل هزینه ، درخت پوشایی است که دارای کمترین هزینه باشد.
برای به دست آوردن درخت پوشای حداقل هزینه یک گراف وزن دارمتصل می توان از سه الگوریتم متفاوت استفاده نمود :
الگوریتم کراسکل، الگوریتم پریم ، الگوریتم سولین
هر سه روش از یک طراحی الگوریتمی به نام خط مشی greedy استفاده می کنند.
اسلاید ۳ :
۳-۶ درختان پوشای با حداقل هزینه
برای درخت های پوشا از ملاک کمترین هزینه استفاده می شود. روش ما باید دارای شرایط زیر باشد :
(۱باید فقط از لبه های داخل گراف استفاده کنیم.
(۲ باید دقیقا از n-1 لبه استفاده کنیم.
(۳ نباید از لبه هایی که ایجاد یک حلقه می کنند ، استفاده کنیم.
