درخت (نظریه گراف): تفاوت میان نسخه‌ها

جز
ربات: ویرایش جزئی
جز (ربات: اصلاح حمزهٔ بعد از "ه")
جز (ربات: ویرایش جزئی)
 
[[پرونده:Tree graph.svg|left]]
در [[نظریهٔ گراف]]، '''درخت''' گرافی است که هر دو [[رأس]] آن با دقیقا یک [[مسیر]] به هم متصل شده است. همچنین، هر گراف [[متصل]] که [[مدار]] نداشته باشد یک درخت است. جنگل، اجتماع چندین درخت است. درخت ها به طور گسترده در [[علوم کامپیوتر]] و [[ساختار داده‌ها]] کاربرد دارند مثل [[درخت‌های جستجوی دودویی]]، [[پشته‌ها]]<ref>Heaps</ref>، درخت‌های هافمن<ref>Huffman trees</ref> برای [[فشرده‌سازی اطلاعات]] و غیره.
 
 
== تعاریف ==
[[تصویرپرونده:Tree1.png|thumb|200px|left|نمونه‌ای از یک درخت]]
[[تصویرپرونده:Tree2.png|thumb|200px|left|در اینجا بدلیل وجود یک دور گراف درخت نمی‌باشد.]]
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
*G متصل است و دور ندارد.
*هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل می‌شوند.
 
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
 
*G متصل است و n-1 یال دارد.
[[درخت جهت‌دار]]<ref>Directed tree</ref> گراف جهت‌داری است که اگر جهت روی یال‌های آن را نادیده بگیریم به یک درخت تبدیل می‌شود.
 
یک درخت را ریشه‌دار<ref>Rooted tree</ref> گوییم اگر یک رأس در آن ریشه باشد. مرتبهٔ درخت<ref>tree-order</ref> یک [[مرتب‌سازی جزئی]]<ref>partial ordering</ref> روی رئوس درخت است که <math>u\le v</math> اگر و فقط اگر یک مسیر یکتا از ریشه به v از u بگذرد. یک درخت که زیر گراف، گراف G است را درخت نرمال<ref>Normal tree</ref> گوییم اگر انتهای هر یال G با این رتبه بندی قابل مقایسه باشد ( Diestel 2005 ,p.15 ).
 
درخت ریشه‌دار یک ساختار داده کلیدی در علوم کامپیوتر است. در ضمن با توجه به این که فرض می‌شود درخت‌ها ریشه دارند یک درخت بدون ریشه را درخت آزاد<ref>Free 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}}
 
۱۸۶٬۰۵۸

ویرایش