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

جز (حذف رده «درخت‌ها (نظریه گراف)» (با استفاده از رده‌ساز))
 
== تعاریف ==
[[تصویر:Tree1.png|thumb|200px|left|نمونه‌ای از یک درخت]]
[[تصویر:Tree2.png|thumb|200px|left|در اینجا بدلیل وجود یک دور گراف درخت نمی‌باشد.]]
درخت یک گراف ساده بدون جهت است که در یکی ار شروط معادل زیر صدق کند:
*G متصل است و دور ندارد.
*G هیج مداری ندارد و اگر یک یال به آن اضافه شود یک مدار ساده در آن بوجود می آیدمی‌آید.
*G متصل است و اگر یک یال آن خذف شود دیگر متصل نیست.
*G متصل است و گراف کامل 3 رأسی <math>K_3</math> جزِئی از آن نیست.
*هر دو رأس در G با یک مسیر سادهٔ یکتا به هم وصل می شوندمی‌شوند.
 
اگر G تعداد متناهی رأس داشته باشد احکام بالا با شروط زیر نیز معادل اند:
گراف سادهٔ بدون جهت G را جنگل<ref>forest</ref> گوئیم اگر مسیر ساده نداشته باشد.
 
[[درخت جهت‌دار]]<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 است. )
 
درخت ساده نشدنی<ref>irreducible tree</ref> درختی است که رأسی با درجه ی 2 ندارد.
 
درخت مرتب<ref>Ordered tree</ref> درختی است که برای فرزندان هر رأس مرتبه ایمرتبه‌ای تعیین شده باشد.
 
درخت n-تایی درختی است که هر رأس که برگ نیست حداکثر n فرزند دارد.
 
درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر ساده ی یکتا که رأس 2 را به 6 وصل می کندمی‌کند 6-5-4-2 است.
 
==احکام==