درخت (نظریہ گراف)

آزاد دائرۃ المعارف، ویکیپیڈیا سے
Jump to navigation Jump to search
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 سے نکلنے والے ہر ذیلی گراف کے راس گِنو اور ان میں سب سے بڑے تعداد کو کہو۔ اب یا تو صرف ایک قمہ a ایسا ہو گا جس کے لیے Cnetroid of a tree graph.svg

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

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

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

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

مزید دیکھیے[ترمیم]

==بیرونی روابط ==*

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