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

''از طریق تناقض'': به ازای هر درخت فراگیر <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>