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

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

مسلئہ اثباتی

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

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

فائل:Graph and its spanning trees.svg

گراف اور اس کے نیچے اس کے دو عبری درخت دکھائے گئے ہیں

مدیدی درخت

مدیدی درخت کسی متصل گراف 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}$ ہے۔

مزید دیکھیے

• رستہ

==بیرونی روابط ==* سانچہ:ریاضی مدد سانچہ:زمرہ کومنز