درخت (نظریہ مخطط)

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
Tree graph.svg
اصطلاح term

مُخطط
قِمّہ، اقمات
کنارہ
درخت
مدیدی
دورہ
شاخ
مرکزی
دومرکزی

graph
vertex, vertices
edge
tree
spanning
cycle
branch
central
bicentral

ریاضی کی شاخ نظریۂ مخطط میں ایسا مخطط جس میں کوئی دورہ نہ ہو کو درخت کہا جاتا ہے۔ دوسرے الفاظ میں درخت مخطط کی ہر دو اقمات صرف ایک کنارے سے جڑی ہوتی ہیں۔ درخت کے کنارہ کو شاخ بھی کہا جاتا ہے۔ درخت مخطط کی سادہ ترین قسم ہے اور عملی طور پر بہت مفید ہے۔ n اقمات پر مشتمل درخت کے n-1 کنارے ہوتے ہیں۔ n اقمات کے درخت میں مزید ایک قمہ اور ایک کنارہ کا اضافہ کر کے n+1 اقمات کا درخت بنایا جا سکتا ہے۔

مسلئہ اثباتی[ترمیم]

درخت T کی اقمات کی تعداد n ہو۔ تو نیچے دیے بیانات برابر ہیں:

  • درخت T متصل ہے اور اس میں کوئ دورہ‌ے نہیں۔
  • درخت T متصل ہے اور کناروں کی تعداد n-1 ہے
  • درخت T کے کناروں کی تعداد n-1 ہے اور اس میں کوئ دورہ‌ے نہیں
  • درخت T متصل ہے اور ہر کنارہ پُل ہے
  • درخت T کی کوئ بھی دو اقمات صرف ایک رستہ سے جڑی ہیں
  • درخت T میں کوئ دورہ‌ے نہیں، مگر اگر ایک نیا کنارہ کا اضافہ کیا جائے (بغیر کسی نئ قمہ کے) تو صرف ایک دورہ پیدا ہوتا ہے
مخطط اور اس کے نیچے اس کے دو عبری درخت دکھائے گئے ہیں

مدیدی درخت[ترمیم]

مدیدی درخت کسی متصل مخطط G کا ایسا ذیلی مخطط ہوتا ہے جس میں G کی تمام اقمات ہوں اور یہ درخت بھی ہو۔ تصویر میں متصل مخطط اور اس کے دو درخت دکھائے گئے ہیں۔ غور کرو کہ مخطط کے ممکنہ درختوں کی تعداد کافی زیادہ ہو سکتی ہے۔ متصل مخطط سے مدیدی درخت حاصل کرنے کا طریقہ یہ ہے کہ مخطط میں دورہ ڈھونڈو اور دورہ کا ایک کنارہ ہٹا دو۔ اس طرح یہ عمل جاری رکھو جب تک تمام دورہ‌ے ختم ہو جائیں، تو مخطط کا مدیدی درخت حاصل ہو جائے گا۔ (دیکھو صغیر مدیدی درخت)

مرکز اور دومرکز[ترمیم]

ہر درخت کا مرکز ایک قمہ ہوتا ہے یا پھر دو قمہ اور ان کو جوڑنے والا کنارہ جسے دومرکز کہتے ہیں۔ ان کو ڈھونڈنے کا طریقہ یہ ہے: درخت کے اقمات کی تعداد n ہو۔ ہر قمہ جس کا درجہ 2 یا زیادہ ہو، اس قمہ a سے نکلنے والے ہر ذیلی مخطط کے اقمات گِنو، اور ان میں سب سے بڑے تعداد کو n_a کہو۔ اب یا تو صرف ایک قمہ a ایسا ہو گا جس کے لیے Cnetroid of a tree graph.svg

n_a \le \frac{n-1}{2}

یہ قمہ مرکز ہے۔ اس درخت کو مرکزی درخت کہتے ہیں۔ یا پھر دو اقمات a اور b ایسے ہوں گے جن کے لیے Bicentroid of a tree graph.svg

n_a=n_b=\frac{n}{2}

اور یہ دو اقمات دومرکز ہوں گے۔ اس درخت کو دومرکزی درخت کہتے ہیں۔


درختوں کی گنتی[ترمیم]

کیلے مسلئہ اثباتی: ایسے ملصق درخت جس میں n اقمات ہوں کی ممکنہ تعداد n^{n-2} ہے۔

اور دیکھو[ترمیم]

بیرونی روابط[ترمیم]

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