دانلود فایل پاورپوینت اجزای دو اتصالی و نقاط اتصال

PowerPoint قابل ویرایش
10 صفحه
8900 تومان

لطفا به نکات زیر در هنگام خرید دانلود فایل پاورپوینت اجزای دو اتصالی و نقاط اتصال توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت اجزای دو اتصالی و نقاط اتصال قرار داده شده است

2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

4-در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

— پاورپوینت شامل تصاویر میباشد —-

اسلاید ۱ :

۲-۶ اجزای دو اتصالی و نقاط اتصال

نقطه اتصال : یک راس مانند v از گراف G می باشد به نحوی که حذف راس v همراه با تمام لبه های متلاقی با v ، گرافی به نام          ایجادمی کند که حداقل دارای دو جز متصل است.

گراف دو اتصالی یک گراف متصل است اگر فاقد نقاط اتصالی باشد .

اسلاید ۲ :

۳-۶ درختان پوشای با حداقل هزینه

هزینه یک درخت پوشای یک گراف دارای وزن ، مجموع هزینه های (وزن های) لبه ها در درخت پوشا می باشد.

درخت پوشای حداقل هزینه ، درخت پوشایی است که دارای کمترین هزینه باشد.

برای به دست آوردن درخت پوشای حداقل هزینه یک گراف وزن دارمتصل می توان از سه الگوریتم متفاوت استفاده نمود :

الگوریتم کراسکل، الگوریتم پریم ، الگوریتم سولین

هر سه روش از یک طراحی الگوریتمی به نام خط مشی greedy استفاده می کنند.

اسلاید ۳ :

۳-۶ درختان پوشای با حداقل هزینه

برای درخت های پوشا از ملاک کمترین هزینه استفاده می شود. روش ما باید دارای شرایط زیر باشد :

باید فقط از لبه های داخل گراف استفاده کنیم.

باید دقیقا از n-1 لبه استفاده کنیم.

نباید از لبه هایی که ایجاد یک حلقه می کنند ، استفاده کنیم.

اسلاید ۴ :

۳-۶ الگوریتم کراسکل

در این روش ، درخت پوشای با کمترین هزینه T ، لبه به لبه ساخته می شود. لبه های مورد استفاده در T ، به ترتیب صعودی وزن ها می باشد. یک لبه در T خواهد بود، اگر با لبه های قبل که در T بوده اند ، تشکیل یک حلقه ندهد چون G متصل است و دارای n > 0 راس است ، دقیقا n ۱ لبه برای T انتخاب می شود.

این الگوریتم با نام راشال نیز شناخته شده است

 

اسلاید ۵ :

۳-۶ الگوریتم کراسکل(راشال)

قضیه

فرض کنید G یک گراف متصل وزن دار باشد ، الگوریتم راشال یک درخت پوشای حداقل را ایجاد می کند.

اسلاید ۶ :

۳-۶ الگوریتم پریم

الگوریتم پریم مانند الگوریتم کراسکل، در هر زمان یک لبه از درخت پوشای حداقل هزینه را می سازد.

هر چند در هر مرحله الگوریتم پریم، مجموعه لبه ها انتخاب شده یک درخت را تشکیل می دهند . در مقابل ، مجموعه لبه های انتخاب شده در الگوریتم کراسکل در هر مرحله یک جنگل را تشکیل می دهند.

 الگوریتم پریم با یک درخت مانند T ، که تنها شامل یک راس است، شروع می کند. این می تواند هر یک از رئوس در گراف اصلی باشد.

 سپس یک لبه با کمترین هزینه مانند               به T اضافه می شود به نحوی که                       از خود یک درخت می باشد. این عمل را تا زمانی که T شامل n ۱ لبه باشد ، ادامه می دهیم.

اسلاید ۷ :

۳-۶ الگوریتم سولین

بر خلاف الگوریتم پریم و راشال ، الگوریتم سولین چندین لبه را برای اضافه نمودن در هر مرحله انتخاب می کند. در ابتدا یک مرحله ، لبه های انتخاب شده ، همراه با تمام n راس گراف ، تشکیل یک درخت پوشا را می دهند. در خلال یک مرحله یک لبه برای هر درخت در جنگل انتخاب می کنیم. این لبه دارای حداقل هزینه بوده یعنی دقیقا دارای یک راس در درخت می باشد. از آنجا که دو درخت در جنگل می توانند یک لبه یکسان انتخاب کنند ، لذا می توانیم کپی تکراری از لبه ها را حذف کنیم. در ابتدای مرحله اول ، مجموعه لبه های انتخاب شده خالی می باشد. این الگوریتم هنگامی به پایان می رسد که فقط یک درخت در انتهای یک مرحله باقی و یا هیچ لبه ای برای انتخاب باقی نمانده باشد.

 

مطالب فوق فقط متون اسلاید های ابتدایی پاورپوینت بوده اند . جهت دریافت کل ان ، لطفا خریداری نمایید .
PowerPointقابل ویرایش - قیمت 8900 تومان در 10 صفحه
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد