الگوریتم کراسکال: تفاوت میان نسخه‌ها

 

به عنوان مثال فرض کنید یک شبکه [[راه آهن]] که تعدادی شهر را به یکدیگر متصل می‌کند در دست احداث است می‌خواهیم با داشتن هزینه<math>{c_{ij}}</math> مربوط به احداث خط مستقیم بین شهرهای <math>{v_i},{v_j}</math> شبکه را طوری طراحی کنیم که مجموع هزینه‌های ساخت به کمترین مقدار خود برسد. با در نظر گرفتن هر شهر به عنوان یک راس از گراف وزن دار با وزن‌های <math>w({v_i},{v_j})={c_{ij}}</math> مسئله به یافتن یک زیر گراف فراگیر همبند با کمترین وزن در یک گراف منجر می‌شود.

فرض کنید وزن‌ها نامنفی هستند بنابراین می‌توانیم تصور کنیم که زیر گراف فراگیر با کمترین وزن یک درخت فراگیر <math>T</math> از <math>G</math> است حال الگوریتم زیر را برای این کار ارائه می‌دهیم.

 

 

۱-یال پیوندی<math>e_1</math> را طوری انتخاب کن که وزن آن کوچکترین مقدار موجود باشد.

 

== اثبات ==

 

''از طریق تناقض'': به ازای هر درخت فراگیر <math>T</math> از <math>G</math> به غیر از <math>U</math> کوچکترین مقدار <math>i</math> را به طوری که <math>{e_i}</math> در <math>T</math> نباشد با<math>f(t)</math> نمایش می‌دهیم.

<math>w({T^'})=w(T)+w({e_k})-w({{e^'}_k})</math>

 

 

<math>w({{e^'}_k})</math> ≥ <math>w({{e}_k}),</math>

که این با <math>T</math> انتخاب در تناقض است. بنابرین <math>T=U</math> و در نتیجه<math> U</math> یک درخت بهینه‌است.

 

 

مسئله:یک درخت پوشای می نیمم مشخص کنید.