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

یک درخت را ریشه‌دار<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>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 ندارد.

درخت نمایش داده شده در شکل بالا 6 رأس، 1 -6 = 5 یال دارد. مسیر ساده یسادهٔ یکتا که رأس 2 را به 6 وصل می‌کند 6-5-4-2 است.