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

در [[نظریه گراف]]، '''الگوریتم کروسکال''' الگوریتمی برای یافتن یک [[زیرگراف]] فراگیر [[گراف همبند|همبند]] با کمترین وزن در یک [[گراف وزن‌دار]] است (در یک گراف وزن دار، به هر یال وزنی نسبت داده شده‌است). همچنین این الگوریتم برای یافتن کوچکترین درخت فراگیر در یک گراف وزن دار استفاده می‌شود.

 

 

فرض کنید وزن‌ها نامنفی هستند بنابراین می‌توانیم تصور کنیم که زیر گراف فراگیر با کمترین وزن یک درخت فراگیر <math>T</math> از <math>G</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>U</math> یک [[درخت]] بهینه نباشد و <math>T</math> را به عنوان درخت بهینه در نظر بگیرید که در آن<math>f(t)</math> دارای بزرگترین مقدار ممکن باشد. فرض کنید <math>f(t)=k</math> این بدان معنی است که <math>{e_{k-1}},{...},{e_2},{e_1}</math> هم در <math>T</math> و هم در <math>U</math> هستند. ولی <math>{e_k}</math> در <math>T</math> نیست پس شامل یک دور یکتای <math>C</math> می‌باشد. فرض کنید <math>{{e^'}_k}</math> یالی از <math>C</math> باشد که در <math>T</math> هست ولی در <math>U</math> نیست. پس <math>{{e^'}_k}</math>[[یال برشی]] ازT+<math>{e_k}</math> نیست.

 

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

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

 

 

 

{{چپ‌چین}}

[[رده:الگوریتم‌های گراف]]

[[رده:درخت پوشا]]