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

جز
ربات: اصلاح حمزهٔ بعد از "ه"
جز (ربات: اصلاح فاصله مجازی: "ای" بعد از "ه")
جز (ربات: اصلاح حمزهٔ بعد از "ه")
[[درخت جهت‌دار]]<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 است.
 
==احکام==
۱۸۶٬۰۵۸

ویرایش