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=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات