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