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

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

گراف
راس
کنارہ
درخت
تمدد
مدیدی
دورہ
صغیر
وصیلہ

graph
vertex, vertices
edge
tree
span
spanning
cycle
minimum
connector

لالچی الخوارزمترميم

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

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

مزید دیکھیےترميم

بیرونی روابطترميم

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