"درخت (نظریہ گراف)" کے نسخوں کے درمیان فرق

{{اصطلاح برابر|

مُخطط <br> قِمّہ، اقمات <br>کنارہ <br>درخت <br> مدیدی<br> دورہ <br> شاخ <br>مرکزی <br>دومرکزی|

===مسلئہ اثباتی ===

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

* درخت ''T'' متصل ہے اور کناروں کی تعداد ''n-1'' ہے

* درخت ''T'' متصل ہے اور ہر کنارہ [[پُل (نظریہ مخطط)|پُل]] ہے

* درخت ''T'' کی کوئی بھی دو اقمات صرف ایک [[Path (graph theory|رستہ]] سے جڑی ہیں

 

===مدیدی درخت ===

مدیدی درخت کسی متصل مخطط ''G'' کا ایسا ذیلی مخطط ہوتا ہے جس میں ''G'' کی تمام اقمات ہوں اور یہ درخت بھی ہو۔ تصویر میں متصل مخطط اور اس کے دو درخت دکھائے گئے ہیں۔ غور کرو کہ مخطط کے ممکنہ درختوں کی تعداد کافی زیادہ ہو سکتی ہے۔

 

===مرکز اور دومرکز ===

ہر درخت کا مرکز ایک قمہ ہوتا ہے یا پھر دو قمہ اور ان کو جوڑنے والا کنارہ جسے دومرکز کہتے ہیں۔ ان کو ڈھونڈنے کا طریقہ یہ ہے: درخت کے اقمات کی تعداد ''n'' ہو۔ ہر قمہ جس کا درجہ 2 یا زیادہ ہو، اس قمہ ''a'' سے نکلنے والے ہر ذیلی مخطط کے اقمات گِنو اور ان میں سب سے بڑے تعداد کو <math>n_a</math> کہو۔ اب یا تو صرف ایک قمہ ''a'' ایسا ہو گا جس کے لیے

:<math>n_a \le \frac{n-1}{2}</math>

یہ قمہ مرکز ہے۔ اس درخت کو مرکزی درخت کہتے ہیں۔ یا پھر دو اقمات ''a'' اور ''b'' ایسے ہوں گے جن کے لیے

:<math>n_a=n_b=\frac{n}{2}</math>

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

 

==بیرونی روابط ==* {{ریاضی مدد}}

 

[[زمرہ:نظریہ مخطط]]