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

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