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

ریاضی کی شاخ نظریۂ گراف میں ایسا گراف جس میں کوئی دورہ نہ ہو کو درخت کہا جاتا ہے۔ دوسرے الفاظ میں درخت گراف کی ہر دو راس صرف ایک کنارے سے جڑی ہوتی ہیں۔ درخت کے کنارہ کو شاخ بھی کہا جاتا ہے۔ درخت گراف کی سادہ ترین قسم ہے اور عملی طور پر بہت مفید ہے۔ 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 راس ہوں کی ممکنہ تعداد  ہے۔

 مزید دیکھیے 
 رستہ

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

زمرہ:کامنز زمرہ جس کا ربط ویکی ڈیٹا پر ہے
زمرہ:ویکی ڈیٹا سے مطابقت رکھنے والی مختصر تفصیل
زمرہ:نظریہ گراف