Minimum spanning tree

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
مستوی مخطط کا صغیر عبری درخت۔ ہر کنارہ پر اس کے وزن کا لصق لگا ہے، جو اس کی لمبائی (یا خرچ) کے متناسب ہے۔
اصطلاح 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 پڑھیٔے     ریاضی علامات