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

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت اجزاي دو اتصالي و نقاط اتصال قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 4 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

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

اسلاید ۱ :

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

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

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

اسلاید ۲ :

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

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

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

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

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

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

اسلاید ۳ :

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

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

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

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

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

اسلاید ۴ :

۳-۶ الگوريتم كراسكل

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

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

 

اسلاید ۵ :

۳-۶ الگوريتم كراسكل(راشال)

قضيه

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

اسلاید ۶ :

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

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

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

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

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

اسلاید ۷ :

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

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