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 کے ساتھ اور صغیر مدیدی درخت (سبز نمایاں) ڈھونڈ لیا گیا ہے۔

مزید دیکھیے

بیرونی روابط

E=mc² اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے ریاضی علامات