درخت (نظریه گراف): تفاوت میان نسخهها
محتوای حذفشده محتوای افزودهشده
جز ربات: اصلاح حمزهٔ بعد از "ه" |
جز ربات: ویرایش جزئی |
||
خط ۲:
[[پرونده:Tree graph.svg|left]]
در [[نظریهٔ گراف]]، '''درخت''' گرافی است که هر دو [[رأس]] آن با دقیقا یک [[مسیر]] به هم متصل شده است. همچنین، هر گراف [[متصل]] که [[مدار]] نداشته باشد یک درخت است.
== تعاریف ==
[[
[[
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
*G متصل است و دور ندارد.
خط ۱۵:
*هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل میشوند.
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر
*G متصل است و n-1 یال دارد.
خط ۲۳:
[[درخت جهتدار]]<ref>Directed tree</ref> گراف جهتداری است که اگر جهت روی یالهای آن را نادیده بگیریم به یک درخت تبدیل میشود.
یک درخت را ریشهدار<ref>Rooted tree</ref> گوییم اگر یک رأس در آن ریشه باشد.
درخت ریشهدار یک ساختار داده
درخت چندگانه<ref>Polytree</ref> درختی است که حداکثر یک مسیر بدون جهت بین هر دو رأسش دارد.
درخت برچسب دار<ref>Labeled tree</ref> درختی است که در آن هر رأس برچسب یکتایی دارد. رئوس درختی با n رأس به طور نمونه با اعداد 1و2و3و...وn برچسب گذاری میشوند. درخت بازگشتی<ref>Recursive tree</ref> یک درخت ریشه دار با برچسب است که برچسب رئوس باتوجه به مرتبهٔ درخت تعیین میشود.( اگر <math>u<v</math> و u,v دو رأس درخت باشند برچسب u کوچکتر از برچسب v است. )
خط ۳۹:
درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر سادهٔ یکتا که رأس 2 را به 6 وصل میکند 6-5-4-2 است.
== احکام ==
*هر درخت یک گراف دو بخشی<ref>bipartite graph</ref> و یک گراف میانه<ref>Median graph</ref> است. هر درخت با تعداد شمارا رأس یک گراف مسطح است.
*هر درخت با <math>n\le 2</math> حداقل 2 برگ ( یا رأس با درجه 1)دارد. حداقل تعداد برگ مربوط به گراف مسیر<ref>Path graph</ref> و حداکثر تعداد برگ (n-1) مربوط به گراف ستارهای است.
*بین هر سه رأس در یک درخت سه مسیر وجود دارد که این سه مسیر حداقل در یک رأس مشترک اند.
== منابع ==
* .Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4
* Otter, Richard (1948), “The Number of Trees”, Annals of Mathematics, Second Series 49 (3): 583–599
== پاورقی ==
{{reflist}}
|