"درخت (نظریہ گراف)" کے نسخوں کے درمیان فرق
حذف شدہ مندرجات اضافہ شدہ مندرجات
کوئی خلاصۂ ترمیم نہیں |
کوئی خلاصۂ ترمیم نہیں |
||
سطر 1:
[[Image:Tree_graph.svg|thumb|left|180px]]
{{اصطلاح برابر|
مُخطط <br> قِمّہ، اقمات <br>کنارہ <br>درخت <br> عبری<br> دورہ <br> شاخ <br>مرکزی <br>دومرکزی|
graph <br> vertex, vertices <br> edge<br> tree <br> spanning <br> cycle <br> branch <br> central <br> bicentral}}
ریاضی کی شاخ نظریۂ مخطط میں ایسا [[مخطط (ریاضی)|مخطط]] جس میں کوئی [[Walk (graph theory|دورہ]] نہ ہو کو ''درخت'' کہا جاتا ہے۔ دوسرے الفاظ میں درخت مخطط کی ہر دو اقمات صرف ایک کنارے سے جڑی ہوتی ہیں۔ درخت کے کنارہ کو ''شاخ'' بھی کہا جاتا ہے۔ درخت مخطط کی سادہ ترین قسم ہے اور عملی طور پر بہت مفید ہے۔ ''n'' اقمات پر مشتمل درخت کے ''n-1'' کنارے ہوتے ہیں۔ ''n'' اقمات کے درخت میں مزید ایک قمہ اور ایک کنارہ کا اضافہ کر کے ''n+1'' اقمات کا درخت بنایا جا سکتا ہے۔
سطر 19:
متصل مخطط سے عبری درخت حاصل کرنے کا طریقہ یہ ہے کہ مخطط میں دورہ ڈھونڈو اور دورہ کا ایک کنارہ ہٹا دو۔ اس طرح یہ عمل جاری رکھو جب تک تمام دورہے ختم ہو جائیں، تو مخطط کا عبری درخت حاصل ہو جائے گا۔
===مرکز اور دومرکز ===
ہر درخت کا مرکز ایک قمہ ہوتا ہے یا پھر دو قمہ اور ان کو جوڑنے والا کنارہ جسے دومرکز کہتے ہیں۔ ان کو ڈھونڈنے کا طریقہ یہ ہے: درخت کے اقمات کی تعداد ''n'' ہو۔ ہر قمہ جس کا درجہ 2 یا زیادہ ہو، اس قمہ ''a'' سے نکلنے والے ہر ذیلی مخطط کے اقمات گِنو، اور ان میں سب سے بڑے تعداد کو <math>n_a</math> کہو۔ اب یا تو صرف ایک قمہ ''a'' ایسا ہو گا جس کے لیے
[[Image:Cnetroid_of_a_tree_graph.svg]]
:<math>n_a \le \frac{n-1}{2}</math>
یہ قمہ مرکز ہے۔ اس درخت کو مرکزی درخت کہتے ہیں۔ یا پھر دو اقمات ''a'' اور ''b'' ایسے ہوں گے جن کے لیے
[[Image:Bicentroid_of_a_tree_graph.svg]]
:<math>n_a=n_b=\frac{n}{2}</math>
اور یہ دو اقمات دومرکز ہوں گے۔ اس درخت کو دومرکزی درخت کہتے ہیں۔
===درختوں کی گنتی ===
[[Cayley|کیلے]] مسلئہ اثباتی: ایسے ملصق درخت جس میں ''n'' اقمات ہوں کی ممکنہ تعداد <math>n^{n-2}</math> ہے۔
==اور دیکھو ==
| |||