Minimum spanning tree

مستوی مخطط کا صغیر عبری درخت۔ ہر کنارہ پر اس کے وزن کا لصق لگا ہے، جو اس کی لمبائی (یا خرچ) کے متناسب ہے۔

اصطلاح	term
مُخطط قِمّہ، اقمات کنارہ درخت تمدد مدیدی دورہ صغیر وصیلہ	graph vertex, vertices edge tree span spanning cycle minimum connector

ریاضی کی شاخ نظریۂ مخطط میں وزن شدہ مُخطط کا ایسا مدیدی درخت جس کا وزن کم سے کم ہو، کو صغیر مدیدی درخت کہا جاتا ہے۔ اس کو صغیر وصیلہ بھی کہا جاتا ہے۔ فرض کرو کہ ہمیں مختلف علاقوں میں قائم برقی بجلی گھروں کو تاریں بچھا کر ملانا ہے۔ یہ بجلی گھر مخطط کے اقمات ہوں گے۔ دو بجلی گھروں کو ملانے کا خرچ ان اقمات کے درمیان کنارے کا وزن ہے۔ کچھ علاقوں کو ملانا جغرافیائی یا سیاسی اعتبار سے مہنگا یا ناممکن ہو سکتا ہے۔ اس کا سستہ تریں حل مطلوب ہے جو کہ "صغیر وصیلہ" ہے۔

لالچی الخوارزم [ترمیم]

کسی مخطط کا صغیر مدیدی درخت نکالنے کا مشہور الخوارزم کرُسکال (Kruskal) نے پیش کیا جو کہ ایک لالچی الخوارزم ہے۔ اسے لالچی اس لیے کہتے ہیں کیونکہ یہ ہر مرحلہ پر کم ترین خرچہ والی صورت کا انتخاب کرتا ہے، بغیر دیکھے کہ اس کا دوسری جگہوں پر کیا اثر ہو گا۔ ہر مرحلہ پر کم از کم وزن والے کنارے کا انتخاب کیا جاتا ہے بشرطیکہ اس انتخاب سے اب تک بننے والے درخت میں دورہ نہ بنتا ہو۔ اس الخوارزم کو ہم مثال کے ذریعہ واضح کرتے ہیں:

	یہ ہمارا اصل مخطط ہے۔ کناروں کے نزدیک عدد ان کے وزن ہیں۔ کوئی کنارہ نمایاں نہیں کیا گیا۔
	ADاور CE کم ترین کنارے ہیں وزن 5 کے ساتھ۔ ہم AD کا اپنی مرضی سے انتخاب کرتے ہیں اور اسے سبز میں تمایاں کرتے ہیں۔
	CE اب کم ترین ہے جو دورہ نہیں بناتا، وزن 5، اسے ہم دوسرے کنارے کے بطور نمایاں کرتے ہیں۔
	اگلا کنارہ DF وزن 6 کے ساتھ، کو اب اسی طریقہ سے نمایاں کیا گیا ہے۔
	اگلے کم ترین کنارے AB اور BE ہیں، وزن 7 کے ساتھ۔ AB کا انتخاب مرضی سے کیا گیا اور اسے نمایاں کیا گیا۔ کنارہ BD کو سرخ میں نمایاں کیا گیا کیونکہ B اور D کے درمیاں پہلے ہی سبز راستہ ہے (اگر BD کو منتخب کیا جاتا تو ABD دورہ بن جاتا)۔
	اسی طرح BE کو سبز نمایاں کیا جاتا ہے۔ جو کنارے اس مرحلہ پر دورہ بنائیں گے انھیں سرخ نمایاں کیا جاتا ہے۔
	آخر کار عمل تکمیل کو پہنچتا ہے، کنارہ EG وزن 9 کے ساتھ، اور صغیر مدیدی درخت (سبز نمایاں) ڈھونڈ لیا گیا ہے۔