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

اصطلاح	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 ایسا ہو گا جس کے لیے